在 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
广告