Problem: 2749. 得到整數零需要執行的最少操作數

整體思路

這段代碼旨在解決一個具有數學和位運算性質的問題：給定兩個整數 num1 和 num2，找到最小的正整數 k，使得 num1 可以表示為 k 個整數的和，其中每個整數的形式都是 num2 + 2^i（i >= 0）。如果找不到這樣的 k，則返回 -1。

該算法將問題進行了巧妙的數學轉換，然后通過一個循環來枚舉并檢驗所有可能的 k 值。

1. 問題的數學轉換：

   • 題目要求 num1 = (num2 + 2^{i_1}) + (num2 + 2^{i_2}) + ... + (num2 + 2^{i_k})。
   • 將上式重新整理，可以得到 num1 = k * num2 + (2^{i_1} + 2^{i_2} + ... + 2^{i_k})。
   • 進一步變形，我們得到 num1 - k * num2 = 2^{i_1} + 2^{i_2} + ... + 2^{i_k}。
   • 令 x = num1 - k * num2。問題就轉化為了：找到最小的正整數 k，使得 x 可以表示為 k 個 2的冪的和。

2. x 的性質與約束：

   • 一個正整數 x 可以表示為 m 個 2的冪的和，當且僅當 x 的二進制表示中 1 的個數（即 Long.bitCount(x)）小于或等于 m，并且 x 本身 大于或等于 m。
     • Long.bitCount(x) <= m：Long.bitCount(x) 是將 x 表示為 2的冪的和所需的最少項數。例如，7 (111_2) = 4+2+1，最少需要3個2的冪。我們可以通過將一個大的2的冪拆分成兩個小的（如 2^i = 2^{i-1} + 2^{i-1}）來增加項數。所以，只要 m 不小于最少項數，就總能湊出 m 項。
     • x >= m：因為每個 2的冪 2^i 至少是 1 (2^0)，所以 m 個 2的冪的和至少是 m。因此 x 必須大于或等于 m。

3. 算法的枚舉與檢驗邏輯：

   • 基于以上的轉換和性質，算法現在只需要找到最小的正整數 k，滿足以下兩個條件：
     a. x = num1 - k * num2 >= k
     b. Long.bitCount(x) <= k
   • 枚舉 k：代碼通過一個 for 循環，從 k=1 開始枚舉。
   • 循環上限：循環的上限設置為 60。這是一個基于 num1 和 num2 的數據范圍（通常是 10^9 級別）得出的一個足夠大的、安全的上界。2^60 已經遠超 10^18，通常可以覆蓋 long 類型的計算范圍。
   • 檢驗：在每次循環中：
     • 計算 x = num1 - 1L * num2 * k。使用 long 類型是為了防止計算過程中發生整數溢出。
     • 檢查第一個條件 x < k。如果不滿足（注意代碼中是x<k就continue，這等價于要求x>=k），則這個 k 無效，繼續嘗試下一個。
     • 計算 x 的二進制表示中 1 的個數 min = Long.bitCount(x)。
     • 檢查第二個條件 k >= min。如果滿足，說明當前的 k 是一個有效的解。因為我們是從小到大枚舉 k，所以第一個找到的有效解就是最小的，直接 return k。

4. 無解情況：

   • 如果循環結束（k 從 1 到 60 都試過了）還沒有找到一個有效的 k，那么就認為問題無解，返回 -1。

完整代碼

class Solution {/*** 找到最小的正整數 k，使得 num1 可以表示為 k 個 (num2 + 2^i) 形式的整數之和。* @param num1 目標整數* @param num2 基礎整數* @return 最小的正整數 k，如果不存在則返回 -1*/public int makeTheIntegerZero(int num1, int num2) {// 循環枚舉所有可能的 k 值。// 上限 60 是一個基于數據范圍的經驗值，對于 int 范圍的 num1, num2 足夠。for (int k = 1; k <= 60; k++) {// 步驟 1: 根據數學轉換計算 x = num1 - k * num2// 使用 long 類型防止計算過程中溢出long x = 1L * num1 - 1L * num2 * k;// 步驟 2: 檢驗 k 是否滿足兩個核心條件// 條件 1: x 必須能被表示成 k 個 2的冪的和。// 一個必要條件是 x >= k (因為每個 2^i >= 1)。// 如果 x < k，則當前 k 無效，繼續下一個。if (x < k) {// 原代碼的 continue 邏輯可以合并到下面的 if 判斷中，// 即 if (x >= k && k >= min) { return k; }// 這里為了忠于原代碼結構，保持原樣。continue;}// 計算將 x 表示為 2的冪的和所需的最少項數int min = Long.bitCount(x);// 條件 2: 表示 x 所需的項數必須能夠湊成 k。// 這要求 k 必須大于或等于所需的最少項數 (min)。if (k >= min) {// 因為 k 是從小到大枚舉的，所以第一個滿足條件的 k 就是最小的。return k;}}// 如果循環結束仍未找到解，則返回 -1return -1;}
}

時空復雜度

時間復雜度：O(1)

1. 循環：算法的核心是一個 for 循環，該循環的執行次數是一個固定的常數（從 1 到 60）。
2. 循環內部操作：
   • 在每次迭代中，執行的操作包括：長整型乘法、減法、Long.bitCount()、比較。
   • Long.bitCount() 方法在大多數現代CPU上都有對應的硬件指令（如 POPCNT），其執行時間可以認為是 O(1)。即使是軟件實現，其復雜度也與 long 的位數（64位）相關，是一個常數。
   • 因此，循環內部的所有操作都是常數時間的。

綜合分析：
算法的執行時間是 (一個固定的常數次數) * (常數時間操作)。因此，其時間復雜度為 O(1)。

空間復雜度：O(1)

1. 存儲分析：
   • 算法在執行過程中只使用了幾個基本類型的變量（k, x, min）。
   • 這些變量的數量是固定的，不隨輸入 num1 和 num2 的大小而改變。

綜合分析：
算法沒有使用任何與輸入規模成比例的額外數據結構。因此，其額外輔助空間復雜度為 O(1)。