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
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.
Before moving to better approach lets have some key analysis about this questions and its features:
- 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 <bits/stdc++.h>using namespace std;// function for digit sumint 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 > slong 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 programint main() { long long int n = 1000, s = 100; cout << countInteger(n, s); return 0;} |
Java
// Java Program to find number of integer // such that integer - digSum > simport 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 sumdef 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 coden = 1000s = 100print(countInteger(n, s))# This code is contributed# by Anant Agarwal. |
C#
// C# Program to find number of integer // such that integer - digSum > susing 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
<?php// Program to find number of integer // such that integer - digSum > s// function for digit sumfunction digitSum( $n) {$digSum = 0;while ($n) { $digSum += $n % 10; $n /= 10;}return $digSum;}// function to calculate count of // integer s.t. integer - digSum > sfunction countInteger( $n, $s) {// if n < s no integer possibleif ($n < $s) return 0;// iterate for s range and then // calculate total count of such // integer if starting integer is foundfor ( $i = $s; $i <= min($n, $s + 163); $i++) if (($i - digitSum($i)) > $s) return ($n - $i + 1);// if no integer found return 0return 0;}// Driver Code$n = 1000; $s = 100;echo countInteger($n, $s);// This code is contributed by anuj_67.?> |
Javascript
<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> |
Output :
891
Time complexity: O(min(n,s+163)*n)
Space complexity : O(1)
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
