資料結構
網路
關係型資料庫管理系統
作業系統
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 次瀏覽
