数字与其各位数字之和的差大于s的数字
给定数字的各位数字之和是该数字中所有数字的总和。我们将得到一个数字n和s,我们必须找到1到n范围内所有数字与其各位数字之和的差大于s的数字。我们将使用代码实现两种方法,并讨论时间和空间复杂度。
输入
N = 15, S = 5
输出
6
解释
对于0到9范围内的所有数字,数字与其各位数字之和的差为0。对于10到15,每个数字的差为9。
输入
N = 20, S = 25
输出
0
解释
对于0到9范围内的所有数字,数字与其各位数字之和的差为0。同样,对于10到19范围内的每个数字,数字与其各位数字之和的差为9。
对于20,差为19。
观察
在实现我们的第一个算法之前,让我们看看数字之间的一般趋势。
对于0到9范围内的每个数字,数字与其各位数字之和的差为0。
对于10到19范围内的每个数字,数字与其各位数字之和的差为9。
对于100到109范围内的每个数字,数字与其各位数字之和的差为99。
利用这一观察结果,我们将实现代码。
方法一
在这种方法中,我们将遍历给定范围从1到n,差小于s。
示例
#include <iostream> using namespace std; // function to find the count of numbers with difference of more than s int count(int n, int s){ // base condition if(s == 0){ // 1 to 9 have a difference of 0 return n-9; } else{ // traversing over the number with the gap of 10 int diff = 0; // variable to store the previous difference for(int i = 10; i<n; i += 10){ int cur = i; int digitSum = 0; while(cur){ digitSum += cur%10; cur /= 10; } diff = i-digitSum; if(diff > s){ return n-i+1; } } return 0; } } int main(){ int n = 20; int s = 6; cout<<"The total numbers with the difference between the number and sum of digits are greater than "<< s << " in the range of 1 to "<< n << " are: "; // calling to function cout<<count(n,s)<<endl; return 0; }
输出
The total numbers with the difference between the number and sum of digits are greater than 6 in the range of 1 to 20 are: 11
时间和空间复杂度
上述代码的时间复杂度为O(N*log(N))。我们每次都使用了10的因子来遍历,但这并没有太大的影响。
上述代码的空间复杂度为O(1),因为我们没有使用任何额外的空间。
在之前的方法中,我们通过将数字除以10来实现了观察,但这仍然没有影响,所以现在我们将转向另一种更好的方法。
方法二
在C++语言中,我们可以有最大值为1e18的数字,其中将共有18位数字。假设所有数字都是9,那么我们将得到18 * 9 = 162。因此,数字与其各位数字之和的最大差可以是162。
所有小于s的数字的差都小于s。
所有大于s+162的数字的差都大于它。
因此,我们将遍历从s到n和s + 162的最小值之间的数字,并找到差大于s的数字。
示例
#include <bits/stdc++.h> using namespace std; // function to get the digit sum int digitSum(int cur){ int sum = 0; while(cur){ sum += cur%10; cur /= 10; } return sum; } // function to find the count of number with difference more than s int count(int n, int s){ // getting number minimum of n and s + 163 int mi = min(n, s + 163); for(int i = s; i<= mi; i++){ int sum = digitSum(i); if(i - sum > s){ return n - i +1; } } return 0; } int main(){ int n = 1000; int s = 100; cout<<"The total numbers with the difference between the number and sum of digits are greater than "<< s << " in the range of 1 to "<< n << " are: "; // calling to function cout<<count(n,s)<<endl; return 0; }
输出
The total numbers with the difference between the number and sum of digits are greater than 100 in the range of 1 to 1000 are: 891
时间和空间复杂度
上述代码的时间复杂度为O(log(S)),因为我们只遍历了163个元素并在对数时间内找到了它们的各位数字之和。
上述代码的空间复杂度为O(1),因为我们没有使用任何额外的空间。
Explore our latest online courses and learn new skills at your own pace. Enroll and become a certified expert to boost your career.
结论
在本教程中,我们实现了一个程序,用于查找给定数字n范围内1到n之间所有整数的个数,这些整数的数字与其各位数字之和的差大于给定数字s。我们实现了两种方法,一种时间复杂度为O(N*log(N)),空间复杂度为常数;另一种空间复杂度为常数,时间复杂度为对数。