Given a positive value N, we need to find the count of numbers smaller than N such that the difference between the number and sum of its digits is greater than or equal to given specific value diff.
Examples:
Input : N = 13, diff = 2 Output : 4 Then 10, 11, 12 and 13 satisfy the given condition shown below, 10 – sumofdigit(10) = 9 >= 2 11 – sumofdigit(11) = 9 >= 2 12 – sumofdigit(12) = 9 >= 2 13 – sumofdigit(13) = 9 >= 2 Whereas no number from 1 to 9 satisfies above equation so final result will be 4
We can solve this problem by observing a fact that for a number k less than N,
if k – sumofdigit(k) >= diff then above equation will be true for (k+1) also because we know that sumofdigit(k+1) is not greater than sumofdigit(k) + 1 so, k + 1 - sumofdigit(k + 1) >= k - sumofdigit(k) but we know that right side of above inequality is greater than diff, so left side will also be greater than diff.
So, finally we can say that if a number k satisfies the difference condition then (k + 1) will also satisfy same equation so our job is to find the smallest number which satisfies the difference condition then all numbers greater than this and up to N will satisfy the condition so our answer will be N – smallest number we found.
We can find the smallest number satisfying this condition using binary search so total time complexity of solution will be O(log N)
C++
/* C++ program to count total numbers whichhave difference with sum of digits greaterthan specific value */#include <bits/stdc++.h>using namespace std;// Utility method to get sum of digits of Kint sumOfDigit(int K){ // loop until K is not zero int sod = 0; while (K) { sod += K % 10; K /= 10; } return sod;}// method returns count of numbers smaller than N,// satisfying difference conditionint totalNumbersWithSpecificDifference(int N, int diff){ int low = 1, high = N; // binary search while loop while (low <= high) { int mid = (low + high) / 2; /* if difference between number and its sum of digit is smaller than given difference then smallest number will be on left side */ if (mid - sumOfDigit(mid) < diff) low = mid + 1; /* if difference between number and its sum of digit is greater than or equal to given difference then smallest number will be on right side */ else high = mid - 1; } // return the difference between 'smallest number // found' and 'N' as result return (N - high);}// Driver code to test above methodsint main(){ int N = 13; int diff = 2; cout << totalNumbersWithSpecificDifference(N, diff); return 0;} |
Java
/* Java program to count total numbers which have difference with sum of digits greater than specific value */class Test{ // Utility method to get sum of digits of K static int sumOfDigit(int K) { // loop until K is not zero int sod = 0; while (K != 0) { sod += K % 10; K /= 10; } return sod; } // method returns count of numbers smaller than N, // satisfying difference condition static int totalNumbersWithSpecificDifference(int N, int diff) { int low = 1, high = N; // binary search while loop while (low <= high) { int mid = (low + high) / 2; /* if difference between number and its sum of digit is smaller than given difference then smallest number will be on left side */ if (mid - sumOfDigit(mid) < diff) low = mid + 1; /* if difference between number and its sum of digit is greater than or equal to given difference then smallest number will be on right side */ else high = mid - 1; } // return the difference between 'smallest number // found' and 'N' as result return (N - high); } // Driver method public static void main(String args[]) { int N = 13; int diff = 2; System.out.println(totalNumbersWithSpecificDifference(N, diff)); }} |
Python3
# Python program to count total numbers which# have difference with sum of digits greater# than specific value# Utility method to get sum of digits of Kdef sumOfDigit(K): # loop until K is not zero sod = 0 while (K): sod =sod + K % 10 K =K // 10 return sod# method returns count of# numbers smaller than N,# satisfying difference conditiondef totalNumbersWithSpecificDifference(N,diff): low = 1 high = N # binary search while loop while (low <= high): mid = (low + high) // 2 ''' if difference between number and its sum of digit is smaller than given difference then smallest number will be on left side''' if (mid - sumOfDigit(mid) < diff): low = mid + 1 # if difference between number and its sum # of digit greater than equal to given # difference then smallest number will be on # right side else: high = mid - 1 # return the difference between 'smallest number # found' and 'N' as result return (N - high)# Driver code to test above methodsN = 13diff = 2print(totalNumbersWithSpecificDifference(N, diff)) # This code is contributed by Anant Agarwal. |
C#
// C# program to count total numbers // which have difference with sum of // digits greater than specific value using System;class Test { // Utility method to get sum // of digits of K static int sumOfDigit(int K) { // loop until K is not zero int sod = 0; while (K != 0) { sod += K % 10; K /= 10; } return sod; } // method returns count of numbers // smaller than N, satisfying // difference condition static int totalNumbersWithSpecificDifference(int N, int diff) { int low = 1, high = N; // binary search while loop while (low <= high) { int mid = (low + high) / 2; // if difference between number and // its sum of digit is smaller than // given difference then smallest // number will be on left side if (mid - sumOfDigit(mid) < diff) low = mid + 1; // if difference between number and // its sum of digit is greater than // or equal to given difference then // smallest number will be on right side else high = mid - 1; } // return the difference between // 'smallest number found' // and 'N' as result return (N - high); } // Driver code public static void Main() { int N = 13; int diff = 2; Console.Write(totalNumbersWithSpecificDifference(N, diff)); }}// This code is contributed by nitin mittal |
PHP
<?php// PHP program to count total numbers which// have difference with sum of digits greater // than specific value// method to get sum of digits of Kfunction sumOfDigit($K) { // loop until K is not zero $sod = 0; while ($K) { $sod += $K % 10; $K /= 10; } return $sod;}// method returns count of // numbers smaller than N, // satisfying difference conditionfunction totalNumbersWithSpecificDifference($N, $diff){ $low = 1; $high = $N; // binary search while loop while ($low <= $high) { $mid = floor(($low + $high) / 2); /* if difference between number and its sum of digit is smaller than given difference then smallest number will be on left side */ if ($mid - sumOfDigit($mid) < $diff) $low = $mid + 1; /* if difference between number and its sum of digit is greater than or equal to given difference then smallest number will be on right side */ else $high = $mid - 1; } // return the difference // between 'smallest number // found' and 'N' as result return ($N - $high);}// Driver Code$N = 13;$diff = 2;echo totalNumbersWithSpecificDifference($N, $diff); // This code is contributed by nitin mittal?> |
Javascript
<script>// javascript program to// count total numbers which// have difference with sum// of digits greater// than specific value// method to get sum of digits of Kfunction sumOfDigit(K){ // loop until K is not zero let sod = 0; while (K) { sod += K % 10; K /= 10; } return sod;}// method returns count of// numbers smaller than N,// satisfying difference conditionfunctiontotalNumbersWithSpecificDifference(N, diff){ let low = 1; let high = N; // binary search while loop while (low <= high) { let mid = Math.floor((low + high) / 2); /* if difference between number and its sum of digit is smaller than given difference then smallest number will be on left side */ if (mid - sumOfDigit(mid) < diff) low = mid + 1; /* if difference between number and its sum of digit is greater than or equal to given difference then smallest number will be on right side */ else high = mid - 1; } // return the difference // between 'smallest number // found' and 'N' as result return (N - high);}// Driver Codelet N = 13;let diff = 2;document.write( totalNumbersWithSpecificDifference(N, diff));// This code is contributed by Bobby</script> |
Output:
4
This article is contributed by Utkarsh Trivedi. If you like neveropen and would like to contribute, you can also write an article using write.neveropen.co.za or mail your article to review-team@neveropen.co.za. See your article appearing on the neveropen main page and help other Geeks.
Please write comments if you find anything incorrect, or you want to share more information about the topic discussed above.
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!
