在 C++ 中移除多少位數字才能使一個數字能被 3 整除

給定一個字串形式的數字，你需要找到需要移除多少位數字才能使其能被 3 整除。

我們最多移除兩位數字來使數字能被 3 整除。因此，最多需要移除的數字位數是 2。

讓我們看一些例子。

輸入

92

輸出

1

我們可以移除 2 使其能被 3 整除。

輸入

999

輸出

0

給定的數字本身就能被 3 整除。

演算法

  • 初始化字串形式的數字。

  • 找到數字的和。

  • 如果和能被 3 整除，則返回 0。

  • 如果和不能被 3 整除，並且數字的長度為 1，則我們無法使其能被 3 整除。返回 -1。

  • 迭代數字。

    • 從數字中移除一位數字並檢查其是否能被 3 整除。

    • 如果上述條件滿足，則返回 1。

  • 再次檢查數字的長度。如果長度為 2，則返回 -1。

  • 否則返回 2。

實現

以下是上述演算法在 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;
}

輸出

如果你執行上述程式碼，你將得到以下結果。

1

更新於：2021-10-26

310 次瀏覽

開啟你的 職業生涯

完成課程獲得認證

開始學習
廣告