Tìm số lớn nhất có số chữ số đã cho và tổng các chữ số trong C ++

Trong bài toán này, chúng ta được cho hai giá trị nguyên, N biểu thị số chữ số của một số và tổng biểu thị tổng các chữ số của số đó. Nhiệm vụ của chúng ta là tìm số lớn nhất có số chữ số đã cho và tổng các chữ số .

Hãy lấy một ví dụ để hiểu vấn đề,

Input : N = 3, sum = 15
Output : 960

Phương pháp tiếp cận giải pháp

Một cách đơn giản để giải quyết vấn đề là duyệt qua tất cả các số có N chữ số từ lớn nhất đến nhỏ nhất. Tìm các số tổng của chữ số, nếu nó bằng tổng thì trả về số.

Ví dụ

Chương trình minh họa hoạt động của giải pháp của chúng tôi

#include <iostream>
using namespace std;
int digitSum(int n){
   int sum = 0; 
   while(n){
      sum += n%10; 
      n = n/10;
   }
   return sum;
}
int findLargestNumWithSum(int N, int sum){
   if (sum == 0){
      if(N == 1)
         return -1;
      else
         return -1;
   }
   if (sum > 9*N){
      return -1;
   }
   int num = 1;
   for(int i = 0; i < N; i++) 
      num *= 10;
   while(1){
      if(digitSum(num) == sum){
         return num;
      }
      num -- ;
      if(num == 0)
         return -1;
   }
}
int main(){
   int sum = 25, N = 3;
   cout<<"The largest "<<N<<" digit number with sum "<<sum<<" is "<< findLargestNumWithSum(N, sum);
   return 0;
}

Đầu ra

The largest 3 digit number with sum 25 is 997

Một cách tiếp cận khác để giải quyết vấn đề là sử dụng Cách tiếp cận Tham lam. Chúng tôi sẽ làm điều này bằng cách bắt đầu từ MSB, đặt số cao nhất có thể từ tổng và lấy tổng trừ đi.

Chúng ta thực hiện bước này trong N lần sẽ được số lượng cần thiết. Vì vậy, nếu tổng lớn hơn 9, đặt 9 vào chữ số hiện tại, nếu nó nhỏ hơn 9, đặt tổng cho chữ số hiện tại. Thực hiện quy trình này, đối với tất cả các chữ số từ MSB đến LSB đặt các chữ số.

Ví dụ

Chương trình minh họa hoạt động của giải pháp của chúng tôi

#include <iostream>
using namespace std;
int findLargestNumWithSum(int N, int sum){
   if (sum == 0){
      if(N == 1)
         return -1;
      else
         return -1;
   }
   if (sum > 9*N){
      return -1;
   }
   int num = 0;
   for (int i = 0; i < N; i++){
      if (sum >= 9){
         num += 9;
         sum -= 9;
         if(i < (N - 1)){
            num *= 10;
         }
      }
      else{
         num += sum;
         sum = 0;
         if( i < (N - 1)) 
             num *= 10;
      }
   }
   return num;
}
int main(){
   int sum = 25,
   N = 3;
   cout<<"The largest "<<N<<" digit number with sum "<<sum<<" is "<<findLargestNumWithSum(N, sum);
   return 0;
}

Đầu ra

The largest 3 digit number with sum 25 is 997