Tìm tổng chữ số tối thiểu có thể có sau khi thêm một số d trong C ++

Trong bài toán này, chúng ta được cung cấp hai số n và d. Nhiệm vụ của chúng ta là Tìm tổng chữ số nhỏ nhất có thể có sau khi thêm một số d.

Mô tả sự cố - chúng ta cần giảm thiểu tổng các chữ số bằng cách cộng bội số thứ k của d với n.

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

Đầu vào

n = 5230, d = 54

Đầu ra

1

Giải thích

The number will be 5230 + (2*54) = 5338

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

Một cách tiếp cận đơn giản để giải quyết vấn đề là kiểm tra tất cả các bội số của d từ 1 đến 8, vì bội số thứ 9 sẽ lặp lại. Điều này dựa trên modulo 9, sẽ trả về tổng các chữ số. Vì vậy, a + d * (9k + l) modulo 9 tương đương với a + d * l modulo 9. Do đó, chúng tôi sẽ kiểm tra tất cả các bội số của l * d từ 1 đến 8 và trả về giá trị tối thiểu tìm được.

Một tiến bộ trong chương trình có thể được thực hiện bằng cách sử dụng thực tế rằng tổng chữ số sẽ không bao giờ nhỏ hơn 1, vì vậy nếu chúng ta có tổng chữ số =1, chúng ta sẽ trả về nó.

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

Ví dụ

#include <iostream>
using namespace std;
int calcDigitSum(int n) {
   int i = n % 9;
   if (i == 0)
      return 9;
   else
      return i;
}
int findMinDigitSum(int n, int d) {
   int minSum = 10;
   int number;
   for (int i = 1; i < 9; i++) {
      number = (n + i * d);
      minSum = min(minSum, calcDigitSum(number));
      if(minSum == 1)
         return minSum;
   }
   return minSum;
}
int main() {
   int n = 5230, d = 54;
   cout<<"The minimum possible digitsum after adding the number is "<<findMinDigitSum(n, d);
   return 0;
}

Đầu ra

The minimum possible digitsum after adding the number is 1