在本文中，我们将探讨一个有趣的计算问题 – “使一个数字能被 4 整除所需删除的最少位数”。这个问题是编码竞赛和基于算法的面试中的常见问题，为提高您的问题解决能力提供了极好的练习。
首先，让我们理解问题陈述：我们有一个数字，我们的任务是删除最少数量的数字，使得剩余的数字能被 4 整除。
概念理解
问题出在数论领域。需要理解的一个关键事实是，当且仅当一个数字的最后两位数字能被 4 整除时，该数字才能被 4 整除。这一事实对于解决我们的问题至关重要。
算法说明
解决这个问题的算法涉及以下步骤 –
将数字转换为字符串。
从字符串末尾开始检查最后两个字符组成的数字是否能被 4 整除。
如果是，则返回删除的位数。如果不是，则删除最后一个字符并增加计数。
重复此操作，直到数字能被 4 整除或只剩下一位数字。
示例
这是该算法的 C++ 实现 –
#includeusing 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++ 解决方案。
以上就是使一个数能被4整除，最少需要删除的数字个数的详细内容，更多请关注创想鸟其它相关文章！
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。
如发现本站有涉嫌抄袭侵权/违法违规的内容， 请发送邮件至 chuangxiangniao@163.com 举报，一经查实，本站将立刻删除。
发布者：程序猿，转转请注明出处：https://www.chuangxiangniao.com/p/1445227.html
微信扫一扫 
支付宝扫一扫 
