在 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 次浏览

开启你的 职业生涯

完成课程获得认证

开始学习
广告