數字與其各位數字之和的差大於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))，空間複雜度為常數；另一種空間複雜度為常數，時間複雜度為對數。