Números que tienen una diferencia con la suma de dígitos mayor que s

Se le dan dos valores enteros positivos n y s. Tienes que encontrar el número total de dicho número entero de 1 a n tal que la diferencia del número entero y su suma de dígitos sea mayor que s dado.
Ejemplos: 
 

Input : n = 20, s = 5
Output :11
Explanation : Integer from 1 to 9 have 
diff(integer - digitSum) = 0 but for 10 to 
20 they have diff(value - digitSum) > 5

Input : n = 20, s = 20
Output : 0
Explanation : Integer from 1 to 20 have diff
(integer - digitSum) >  5

El primer enfoque y básico para resolver esta pregunta es verificar todos los enteros que comienzan de 1 a n y para cada verificación si la suma de enteros menos dígitos es mayor que s o no. Esto será muy costoso en tiempo porque tenemos que atravesar de 1 a n y para cada número entero también tenemos que calcular la suma de los dígitos.
Antes de pasar a un mejor enfoque, hagamos un análisis clave sobre estas preguntas y sus características: 
 

• Para el entero más grande posible (por ejemplo, long long int, es decir, 10^18), la suma máxima de dígitos posible es 9*18 (cuando todos los dígitos son nueve) = 162. Esto significa, en cualquier caso, que todos los enteros mayores que s + 162 satisfacen la condición de entero – digitSum > s.
• Todo entero menor que s no puede satisfacer la condición dada con seguridad.
• Todos los enteros dentro de un rango de decenas (0-9, 10-19…100-109) tienen el mismo valor de entero menos digitSum.

Usando las tres características clave anteriores, podemos acortar nuestro enfoque y la complejidad del tiempo de una manera en la que tenemos que iterar solo sobre s a s+163 enteros. Además de verificar todos los enteros dentro del rango, solo verificamos cada décimo entero (por ejemplo, 150, 160, 170 …). 
Algoritmo: 
 

// if n < s then return 0
if n<s 
    return 0
else

    // iterate for s to min(n, s+163)
    for i=s to i min(n, s+163)

        // return n-i+1
        if (i-digitSum)>s
            return (n-i+1)

// if no such integer found return 0
return 0

// Program to find number of integer such that
// integer - digSum  > s
#include <bits/stdc++.h>
using namespace std;
 
// function for digit sum
int digitSum(long long int n) {
  int digSum = 0;
  while (n) {
    digSum += n % 10;
    n /= 10;
  }
  return digSum;
}
 
// function to calculate count of integer s.t.
// integer - digSum > s
 
long long int countInteger(long long int n,
                          long long int s) {
 
  // if n < s no integer possible
  if (n < s)
    return 0;
 
  // iterate for s range and then calculate
  // total count of such integer if starting
  // integer is found
  for (long long int i = s; i <= min(n, s + 163); i++)
    if ((i - digitSum(i)) > s)
      return (n - i + 1);
 
  // if no integer found return 0
  return 0;
}
 
// driver program
int main() {
  long long int n = 1000, s = 100;
  cout << countInteger(n, s);
  return 0;
}

// Java Program to find number of integer
// such that integer - digSum > s
import java.io.*;
 
class GFG
{
    // function for digit sum
    static int digitSum(long n)
    {
        int digSum = 0;
        while (n > 0)
        {
            digSum += n % 10;
            n /= 10;
        }
        return digSum;
    }
 
    // function to calculate count of integer s.t.
    // integer - digSum > s
    public static long countInteger(long n, long s)
    {
        // if n < s no integer possible
        if (n < s)
            return 0;
     
        // iterate for s range and then calculate
        // total count of such integer if starting
        // integer is found
        for (long i = s; i <= Math.min(n, s + 163); i++)
            if ((i - digitSum(i)) > s)
                return (n - i + 1);
     
        // if no integer found return 0
        return 0;
    }
 
    // Driver program
    public static void main(String args[])
    {
            long n = 1000, s = 100;
            System.out.println(countInteger(n, s));
    }
}
 
// This code is contributed by Anshika Goyal.

# Program to find number
# of integer such that
# integer - digSum  > s
 
# function for digit sum
def digitSum(n):
 
    digSum = 0
 
    while (n>0):
        digSum += n % 10
        n //= 10
   
    return digSum
  
# function to calculate
# count of integer s.t.
# integer - digSum > s
  
def countInteger(n, s):
     
    # if n < s no integer possible
    if (n < s):
        return 0
  
    # iterate for s range
    # and then calculate
    # total count of such
    # integer if starting
    # integer is found
    for i in range(s,min(n, s + 163)+1):
        if ((i - digitSum(i)) > s):
            return (n - i + 1)
  
    # if no integer found return 0
    return 0
 
# driver code
n = 1000
s = 100
 
print(countInteger(n, s))
 
# This code is contributed
# by Anant Agarwal.

// C# Program to find number of integer
// such that integer - digSum > s
using System;
 
class GFG
{
    // function for digit sum
    static long digitSum(long n)
    {
        long digSum = 0;
         
        while (n > 0)
        {
            digSum += n % 10;
            n /= 10;
        }
        return digSum;
    }
 
    // function to calculate count of integer s.t.
    // integer - digSum > s
    public static long countInteger(long n, long s)
    {
        // if n < s no integer possible
        if (n < s)
            return 0;
     
        // iterate for s range and then calculate
        // total count of such integer if starting
        // integer is found
        for (long i = s; i <= Math.Min(n, s + 163); i++)
            if ((i - digitSum(i)) > s)
                return (n - i + 1);
     
        // if no integer found return 0
        return 0;
    }
 
    // Driver program
    public static void Main()
    {
            long n = 1000, s = 100;
            Console.WriteLine(countInteger(n, s));
    }
}
 
// This code is contributed by vt_m.

<?php
// Program to find number of integer
// such that integer - digSum > s
 
// function for digit sum
function digitSum( $n)
{
$digSum = 0;
while ($n)
{
    $digSum += $n % 10;
    $n /= 10;
}
return $digSum;
}
 
// function to calculate count of
// integer s.t. integer - digSum > s
 
function countInteger( $n, $s)
{
 
// if n < s no integer possible
if ($n < $s)
    return 0;
 
// iterate for s range and then 
// calculate total count of such
// integer if starting integer is found
for ( $i = $s; $i <= min($n, $s + 163); $i++)
    if (($i - digitSum($i)) > $s)
    return ($n - $i + 1);
 
// if no integer found return 0
return 0;
}
 
// Driver Code
$n = 1000; $s = 100;
echo countInteger($n, $s);
 
// This code is contributed by anuj_67.
?>

<script>
// JavaScript Program to find number of integer
// such that integer - digSum > s
 
    // function for digit sum
    function digitSum(n)
    {
        let digSum = 0;
        while (n > 0)
        {
            digSum += n % 10;
            n /= 10;
        }
        return digSum;
    }
   
    // function to calculate count of integer s.t.
    // integer - digSum > s
    function countInteger(n, s)
    {
        // if n < s no integer possible
        if (n < s)
            return 0;
       
        // iterate for s range and then calculate
        // total count of such integer if starting
        // integer is found
        for (let i = s; i <= Math.min(n, s + 163); i++)
            if ((i - digitSum(i)) > s)
                return (n - i + 1);
       
        // if no integer found return 0
        return 0;
    }
   
 
// Driver Code
 
        let n = 1000, s = 100;
        document.write(countInteger(n, s));
 
// This code is contributed by splevel62.
</script>

Producción : 
 

891

Complejidad de tiempo: O(min(n,s+163)*n)