Số chữ số bị xóa để tạo thành một số chia hết cho 3 trong C ++

Bạn được cung cấp một số trong chuỗi. Bạn cần tìm xem có bao nhiêu chữ số cần xóa đi để nó chia hết cho 3.

Chúng ta tạo một số chia hết bằng cách loại bỏ nhiều nhất 2 chữ số. Vậy, số chữ số lớn nhất cần xóa để chia hết cho 3 là 2.

Hãy xem một số ví dụ.

Đầu vào

92

Đầu ra

1

Chúng ta có thể loại bỏ 2 để chia hết cho 3.

Đầu vào

999

Đầu ra

0

Bản thân số đã cho là số chia hết cho 3.

Thuật toán

• Khởi tạo số trong chuỗi.

• Tìm tổng của số.

• Nếu tổng chia hết cho 3 thì trả về 0.

• Nếu tổng không chia hết cho 3 và độ dài của số là 1 thì chúng ta không thể chia hết cho 3. Trả về -1 .

• Lặp lại số.

  • Xóa một chữ số khỏi số và kiểm tra tính chia hết.

  • Nếu điều kiện trên thỏa mãn, thì trả về 1.

• Kiểm tra độ dài của số một lần nữa. Nếu độ dài là 2, sau đó trả về -1.

• Trả lại khác 2.

Thực hiện

Sau đây là cách thực hiện thuật toán trên trong C ++

#include <bits/stdc++.h>
using namespace std;
int getNumSum(string n) {
   int len = n.length(), sum = 0;
   for (int i = 0; i < len; i++) {
      sum += (int)n[i];
   }
   return sum;
}
int getDigitsCount(string num) {
   int n = num.length();
   int sum = getNumSum(num);
   if (sum % 3 == 0) {
      return 0;
   }
   if (n == 1) {
      return -1;
   }
   for (int i = 0; i < n; i++) {
      int currentDigit = num[i] - '0';
      if (sum % 3 == currentDigit % 3) {
         return 1;
      }
   }
   if (n == 2) {
      return -1;
   }
   return 2;
}
int main() {
   string num = "7536836";
   cout << getDigitsCount(num) << endl;
   return 0;
}

Đầu ra

Nếu bạn chạy đoạn mã trên, thì bạn sẽ nhận được kết quả sau.

1