Files

102 lines
3.1 KiB
Markdown
Raw Permalink Blame History

This file contains ambiguous Unicode characters

This file contains Unicode characters that might be confused with other characters. If you think that this is intentional, you can safely ignore this warning. Use the Escape button to reveal them.

# [2749] Minimum Operations To Make The Integer Zero
## 題目資訊
- **難度**: Medium
- **標籤**: Bit Manipulation, Brainteaser, Enumeration
- **題目連結**: [LeetCode](https://leetcode.com/problems/minimum-operations-to-make-the-integer-zero/)
- **練習日期**: 2025-09-05
## 題目描述
You are given two integers `num1` and `num2`.
In one operation, you can choose integer i in the range `[0, 60]` and subtract `2^i + num2` from `num1`.
Return the integer denoting the *minimum* number of operations needed to make `num1` equal to `0`.
If it is impossible to make `num1` equal to `0`, return `-1`.
## 解題思路
### 初步分析
- 這題主要考察什麼概念?
1. 位元操作 (Bit Manipulation):需要理解二進制表示和位元運算
2. 數學建模:將實際問題轉換為數學等式
3. 枚舉 (Enumeration):嘗試不同的操作次數 k
4. 約束條件判斷:理解多個限制條件的邏輯關係
- 有什麼關鍵限制條件?
1. target ≥ 0
2. bitCount(target) ≤ k
3. k ≤ target
- 預期時間/空間複雜度?
- 時間複雜度O(60 × log(target)) ≈ O(1)
- 空間複雜度O(1)
### 解法概述
1. **解法**:
- 思路:
- 目標:讓 num1 變成 0
- 每次操作num1 = num1 - (2^i + num2)
- k 次操作後num1 - k*num2 - (2^i1 + 2^i2 + ... + 2^ik) = 0
- 重新整理target = num1 - k*num2 = 2^i1 + 2^i2 + ... + 2^ik
- 時間複雜度O(1)
- 空間複雜度O(1)
## 測試案例
### 範例輸入輸出
```
Input: num1 = 3, num2 = -2
Output: 3
Explanation:
We can make 3 equal to 0 with the following operations:
- We choose i = 2 and subtract 22 + (-2) from 3, 3 - (4 + (-2)) = 1.
- We choose i = 2 and subtract 22 + (-2) from 1, 1 - (4 + (-2)) = -1.
- We choose i = 0 and subtract 20 + (-2) from -1, (-1) - (1 + (-2)) = 0.
It can be proven, that 3 is the minimum number of operations that we need to perform.
```
### 邊界情況
- `1 <= num1 <= 10^9`
- `-10^9 <= num2 <= 10^9`
## 學習筆記
### 今天學到什麼?
- 二位元的操作寫法
### 遇到的困難
- 二位元的操作
1. 方法一: 逐位檢查法
- 程式碼:
``` C#
count += (int)(n & 1);
n >>= 1;
```
- 運作原理:
1. n & 1檢查最右邊的位元是否為 1
2. count += (int)(n & 1):如果是 1 就加到計數器
3. n >>= 1把 n 右移一位(去掉已檢查的位元)
4. 重複直到 n 變成 0
2. 方法二: 移除最右邊 1
- 程式碼:
``` C#
count++;
n &= n - 1;
```
- 運作原理:
1. n - 1讓最右邊的 1 變成 0其右邊的 0 都變成 1
2. n & (n - 1):神奇地移除了最右邊的 1
3. count++:每移除一個 1計數器就加 1
4. 重複直到 n 變成 0
### 改善方向
-
### 相關題目
- [#991](https://leetcode.com/problems/broken-calculator) Broken Calculator
- [#1658](https://leetcode.com/problems/minimum-operations-to-reduce-x-to-zero/) Minimum Operations to Reduce X to Zero
---
**總結**:
1. 學習二位元的使用技巧