计数数字与其数字和之间的差值大于特定值的数字-yiteyi-C++库

给定一个正值N，我们需要找到小于N的数的计数，使得数与其位数之和之间的差大于或等于给定的特定值差。例如：

null

Input : N = 13, diff = 2Output : 4Then 10, 11, 12 and 13 satisfy the givencondition shown below,10 – sumofdigit(10) = 9 >= 211 – sumofdigit(11) = 9 >= 212 – sumofdigit(12) = 9 >= 213 – sumofdigit(13) = 9 >= 2  Whereas no number from 1 to 9 satisfies above equation so final result will be 4

建议：请在“上解决” 实践 “首先，在讨论解决方案之前。

我们可以通过观察一个事实来解决这个问题，对于一个小于N的数k，

 if k – sumofdigit(k) >= diff thenabove equation will be true for (k+1)also because we know that sumofdigit(k+1)is not greater than sumofdigit(k) + 1so, 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.

最后，我们可以说，如果一个数k满足差分条件，那么（k+1）也将满足相同的方程，所以我们的工作是找到满足差分条件的最小数，然后所有大于这个，直到N的数都将满足条件，所以我们的答案将是N–我们找到的最小数。我们可以通过二进制搜索找到满足这个条件的最小数，所以解的总时间复杂度为O（logn）

C++

                         /* C++ program to count total numbers which                       
                         have difference with sum of digits greater                       
                         than specific value */                       
                         #include <bits/stdc++.h>                       
                         using                                     namespace                                     std;                       
           
                         // Utility method to get sum of digits of K                       
                         int                                     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 condition                       
                         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 to test above methods                       
                         int                                     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 K                       
                         def                                     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 condition                       
                         def                                     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 methods                       
                         N                                     =                                     13                       
                         diff                                     =                                     2                       
           
                         print                                     (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 K                       
                         function                                     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 condition                       
                         function                                     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 K                       
                         function                                     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 condition                       
                         function                       
                         totalNumbersWithSpecificDifference(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 Code                       
                         let N = 13;                       
                         let diff = 2;                       
                         document.write(                       
                         totalNumbersWithSpecificDifference(N, diff)                       
                         );                       
           
                         // This code is contributed by Bobby                       
           
                         </script>                       

输出：

本文由 乌特卡什·特里维迪 .如果你喜欢GeekSforgek，并想贡献自己的力量，你也可以使用写极客。组织或者把你的文章寄去评论-team@geeksforgeeks.org.看到你的文章出现在Geeksforgeks主页上，并帮助其他极客。如果您发现任何不正确的地方，或者您想分享有关上述主题的更多信息，请写下评论。

文章版权归作者所有，未经允许请勿转载。

THE END

技术文章