数字计数,使得C ++中数字与数字总和之间的差不小于L
我们给定一个数字N和另一个数字L。我们的目标是找到1到N之间的数字,这些数字本身与数字总和之差不少于L。
如果N=23,L=10,则此类数字的计数为4。
23-(2+3)=18,22-(2+2)=18,21-(2+1)=18,20-(2+0)=18。
以上所有数字均符合条件
但是19-(1+9)=9小于L,类似地18,17….1。
让我们用例子来理解
输入-N=30L=19
输出-数字计数,以使数字与其数字总和之间的差不小于L为-1
说明-只有30个满足条件,30-(3+0)=27>19
输入-N=123330L=5466
输出-数字的计数,以使数字与其数字总和之间的差不小于L为-6841
以下程序中使用的方法如下
使用二进制搜索,我们将找到符合条件的第一个数字。如果该数字为num,则该条件对于num+1也是成立的,依此类推。
如果任何当前的中间值都满足该条件,则中间和结尾之间的所有数字也将满足此条件,因此我们可以简单地将end-mid+1加起来进行计数。
将num和L作为长变量。
函数Digit_sum(LLnum)接受一个数字num并返回其数字的总和。
将初始总和设为0。
使用while循环,将提醒num%10添加到total并将num减少10。执行此操作直到num>0。
将总数返回为num的位数。
函数Less_than_L(LLnum,LLL)接受一个数字num和一个数字L并返回Numbers的计数,以使数字和其数字之和之间的差不小于L
将初始计数设为0。
使用while循环实现二进制搜索,其中start=1和end=num。
计算中间数字为temp=(start+end)/2。
如果temp和temp的位数之和之间的差不小于L,则所有大于temp的数字也将满足相同条件。
包括temp在内的此类数字的计数将为num-temp+1。添加此计数。并设置end=temp-1。
否则将start设置为temp+1。
在二进制搜索的末尾,计数将具有数字与数字之和不小于L的数字
返回计数作为结果。
示例
#include <bits/stdc++.h> using namespace std; typedef long long LL; int Digit_sum(LL num){ LL total = 0; while (num > 0){ total += num % 10; num = num/10; z} return total; } LL Less_than_L(LL num, LL L){ LL count = 0; LL start = 1; LL end = num; while (start <= end){ LL temp = (end + start) / 2; LL temp_2 = temp - Digit_sum(temp); if (temp_2 >= L){ count = num - temp + 1; end = temp - 1; } else{ start = temp + 1; } } return count; } int main(){ LL num = 234516; LL L = 235; cout<<"Count of Numbers such that difference between the number and sum of its digits not less than L are: "<< Less_than_L(num, L); return 0; }
输出结果
如果我们运行上面的代码,它将生成以下输出-
Count of Numbers such that difference between the number and sum of its digits not less than L are: 234267