使一個數能被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中文網其他相關文章！