C++ 数字与位数和的差大于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

在这个方法中，我们将以小于s的差值遍历给定范围从1到n。

示例

#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来实现了观察，但仍然没有太大影响，所以现在我们将使用另一种更好的方法。

方法2

在C++语言中，我们可以拥有最大大小为1e18的数字，并且其中将有18位数字。让我们假设所有数字都是9，那么我们将得到18 * 9，即162。因此，数字和数字之间的最大差值可以是162。

• 所有小于s的数字差值都小于s

• 所有大于s+162的数字差值都大于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)，因为我们没有使用任何额外的空间。

结论

在本教程中，我们实现了一个程序，用于找到范围从1到给定数字n的整数的总数，其数字和与数字之间的差大于给定数字s。我们实现了两种方法，一种时间复杂度为O(N*log(N))，空间复杂度为常数，并且第二种方法的空间复杂度为常数，并且时间复杂度为对数。