# Numbers having difference with digit sum more than s

You are given two positive integer value n and s. You have to find the total number of such integer from 1 to n such that the difference of integer and its digit sum is greater than given s.

Examples :

```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
```

## Recommended: Please try your approach on {IDE} first, before moving on to the solution.

The very first and basic approach to solve this question is to check for all integer starting from 1 to n and for each check whether integer minus digit sum is greater than s or not. This will become very time costly because we have to traverse 1 to n and for each integer we also have to calculate the digit sum.

• For the largest possible integer (say long long int i.e. 10^18), the maximum possible digit sum is 9*18 (when all of digits are nine) = 162. This means in any case all the integer greater than s + 162 satisfy the condition of integer – digitSum > s.
• All integer less than s can not satisfy the given condition for sure.
• All the integers within a tens range (0-9, 10-19…100-109) does have same value of integer minus digitSum.

Using above three key features we can shorten our approach and time complexity in a manner where we have to iterate only over s to s+163 integers. Beside checking for all integer within range we only check for each 10th integer (e.g 150, 160, 170..).
Algorithm:

```// 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
```

## C++

 `// Program to find number of integer such that ` `// integer - digSum  > s ` `#include ` `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; ` `} `

/div>

## Java

 `// 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. `

## Python3

 `# 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#

 `// 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

 ` 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. ` `?> `

Output :

```891
```

## tags:

Mathematical number-digits Mathematical