可能的数字削减，以便在C ++中最大部分可以被3整除
在这个问题中，我们得到一个大的整数值（最多105个数字）。我们的任务是打印所需切割的总数，以使最大部分被3整除。
让我们以一个例子来了解问题
输入-9216
输出-3
说明-数字除以9|21|6。
为了解决这个问题，我们必须从数字的最低有效位开始，即数字的最后一位。为此，我们将找到最小的三分之一。然后根据它更新计数。
示例-如果arr[i]将3整除，那么我们将增加计数并移至该数字的下一位。如果arr[i]不能被3整除，那么我们将其与下一位数字合并，并检查3的除数。
3的可除性-如果数字的位数可被3整除，则数字可被3整除。
示例
显示我们解决方案实施情况的程序
#include <bits/stdc++.h>
using namespace std;
int countMaximum3DivisibleNumbers(string number){
int n = number.length();
vector<int> remIndex(3, -1);
remIndex[0] = 0;
vector<int> counter(n + 1);
int r = 0;
for (int i = 1; i <= n; i++) {
r = (r + number[i-1] - '0') % 3;
counter[i] = counter[i-1];
if (remIndex[r] != -1)
counter[i] = max(counter[i], counter[remIndex[r]] + 1);
remIndex[r] = i+1;
}
return counter[n];
}
int main() {
string number = "216873491";
cout<<"The number of 3 divisible number created by cutting "<<number<<" are : " <<countMaximum3DivisibleNumbers(number);
return 0;
}输出结果
The number of 3 divisible number created by cutting 216873491 are : 5
热门推荐
10 八一幼儿祝福语大全简短
11 公司乔迁食堂祝福语简短
12 婚礼结束聚餐祝福语简短
13 儿媳买车妈妈祝福语简短
14 毕业送礼老师祝福语简短
15 同事辞职正常祝福语简短
16 恭贺新婚文案祝福语简短
17 金店立秋祝福语简短英文
18 婆婆高寿祝福语大全简短