数据结构
网络
关系型数据库管理系统
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C语言编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
服装设计
法律研究将数字变为4的倍数所需移除的最小位数
在本文中，我们将探讨一个有趣的计算问题——“将数字变为4的倍数所需移除的最小位数”。这个问题在编码竞赛和基于算法的面试中很常见，并且为提高解决问题的能力提供了极好的练习。
首先，让我们了解问题陈述：我们有一个数字，我们的任务是移除最少的数字，使得剩余的数字可以被4整除。
概念理解
该问题属于数论领域。需要理解的一个关键事实是，一个数字可以被4整除当且仅当由其最后两位数字组成的数字可以被4整除。这个事实对于解决我们的问题至关重要。
算法说明
解决此问题的算法涉及以下步骤：
将数字转换为字符串。
从字符串末尾检查由最后两个字符组成的数字是否可以被4整除。
如果是，则返回已移除的数字个数。如果不是，则移除最后一个字符并递增计数。
重复此过程，直到数字可以被4整除或只剩下一个数字。
示例
以下是算法的程序：
#include <stdio.h>
#include <string.h>
int minRemovals(char* num) {
int n = strlen(num); // Get the length of the string
int count = 0;
for (int i = n - 1; i > 0; i--) {
if ((num[i] - '0' + (num[i - 1] - '0') * 10) % 4 == 0) {
return count; // Return the count if the number is divisible by 4
}
count++;
}
return n - 1; // If no divisible number found, return n - 1
}
int main() {
char num[] = "1351";
printf("Minimum number of digits to be removed to make the number divisible by 4 is: %d\n", minRemovals(num));
return 0;
}
输出
Minimum number of digits to be removed to make the number divisible by 4 is: 3
#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
public class Main {
public static int minRemovals(String num) {
int n = num.length(); // Get the length of the string
int count = 0;
for (int i = n - 1; i > 0; i--) {
if ((num.charAt(i) - '0' + (num.charAt(i - 1) - '0') * 10) % 4 == 0) {
return count; // Return the count if the number is divisible by 4
}
count++;
}
return n - 1; // If no divisible number found, return n - 1
}
public static void main(String[] args) {
String num = "1351";
System.out.println("Minimum number of digits to be removed to make the number divisible by 4 is: " + minRemovals(num));
}
}
输出
Minimum number of digits to be removed to make the number divisible by 4 is: 3
def min_removals(num):
n = len(num) # Get the length of the string
count = 0
for i in range(n - 1, 0, -1):
if (int(num[i]) + int(num[i - 1]) * 10) % 4 == 0:
return count # Return the count if the number is divisible by 4
count += 1
return n - 1 # If no divisible number found, return n - 1
num = "1351"
print(
"Minimum number of digits to be removed to make the number divisible by 4 is:",
min_removals(num))
输出
Minimum number of digits to be removed to make the number divisible by 4 is: 3
在 minRemovals 函数中，我们初始化一个计数器 count 为 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的倍数所需移除的最小数字个数。我们开发了简洁的各种程序，利用了数论的关键见解。
208 次浏览
