数字与其各位数字之和的差大于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)，因为我们没有使用任何额外的空间。

结论

在本教程中，我们实现了一个程序，用于查找给定数字n范围内1到n之间所有整数的个数，这些整数的数字与其各位数字之和的差大于给定数字s。我们实现了两种方法，一种时间复杂度为O(N*log(N))，空间复杂度为常数；另一种空间复杂度为常数，时间复杂度为对数。