在本文中，我们将探讨一个有趣的计算问题 - “使一个数字能被 4 整除所需删除的最少位数”。这个问题是编码竞赛和基于算法的面试中的常见问题，为提高您的问题解决能力提供了极好的练习。
首先，让我们理解问题陈述：我们有一个数字，我们的任务是删除最少数量的数字，使得剩余的数字能被 4 整除。
概念理解
问题出在数论领域。需要理解的一个关键事实是，当且仅当一个数字的最后两位数字能被 4 整除时，该数字才能被 4 整除。这一事实对于解决我们的问题至关重要。
算法说明
解决这个问题的算法涉及以下步骤 -
将数字转换为字符串。
从字符串末尾开始检查最后两个字符组成的数字是否能被 4 整除。
如果是，则返回删除的位数。如果不是，则删除最后一个字符并增加计数。
重复此操作，直到数字能被 4 整除或只剩下一位数字。
示例
这是该算法的 C++ 实现 -
#include<bits/stdc++.h>
using namespace std;
int minRemovals(string num) {
int n = num.size();
int count = 0;
for (int i = n - 1; i > 0; i--) {
if ((num[i] - '0' + (num[i - 1] - '0') * 10) % 4 == 0) {
return count;
}
count++;
}
return n - 1;
}
int main() {
string num = "1351";
cout << "Minimum number of digits to be removed to make the number divisible by 4 is: ";
cout << minRemovals(num) << endl;
return 0;
}
输出
Minimum number of digits to be removed to make the number divisible by 4 is: 3
在 minRemovals 函数中，我们将计数器计数初始化为 0，这将跟踪删除的位数。然后我们从数字（字符串）的末尾开始迭代，检查最后两位数字组成的数字是否能被 4 整除。如果是，我们返回计数；否则，我们返回计数。如果没有，我们增加计数并继续下一次迭代。
main 函数作为我们程序的入口点，我们在其中定义输入数字并打印要删除的最小位数，以使数字能被 4 整除。
测试用例示例
我们以号码 1351 为例。当我们检查最后两位数字（51）时，我们发现它不能被 4 整除。因此，我们删除最后一位数字（1），得到数字 135。我们再次检查，发现最后两位数字（35） ) 仍然不能被 4 整除。因此，我们删除最后一位数字 (5)，留下数字 13。最后两位数字 (13) 不能被 4 整除，所以我们删除最后一位数字 (3)。现在，我们只剩下数字 1，它不能被 4 整除，但我们无法删除更多的数字。因此，需要删除的最少位数为 3。
时间和空间复杂度
该算法的时间复杂度为O(n)，其中n是数字的位数。空间复杂度为 O(1)，因为我们在算法中没有使用任何额外的数据结构。
结论
在本文中，我们深入研究了一个常见的计算问题 - 确定使数字能被 4 整除所需删除的最小位数。我们利用数论的关键见解开发了一个简洁的 C++ 解决方案。
