使一个数能被4整除，最少需要删除的数字个数

在本文中，我们将探讨一个有趣的计算问题 - “使一个数字能被 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++ 解决方案。

以上是使一个数能被4整除，最少需要删除的数字个数的详细内容。更多信息请关注PHP中文网其他相关文章！