---
# System prepended metadata

title: 2749. Minimum Operations to Make the Integer Zero
tags: ["medium\_"]

---

# 2749. Minimum Operations to Make the Integer Zero

## 題目簡述
給你兩個數字 num1 、 num2, 接著 讓 num1 - (2的冪次方 + num2) 若干次，直到 num1 = 0，求若干次，若無法達成則回傳 -1

---

## 思路
一開始還想要靠暴力，但是很明顯牽扯到數字的次方，一定會爆測資，加上題目求特定次數或是極值所以高機率是 DP ，但是這題也不用 DP ，也可以解

如果把 num1 - (2的冪次方 + num2) 若干次 可以整理成

num1 - k*num2 - k個2的冪次方和，所以前面是可以預先處理的，只要判斷該值是否是2的冪次方組合的值就好。

2的冪次方和的可以表示任何數(2的0次方是1，沒有數字不能由奇數、偶數組成)，問題是幾個2的冪次方，數量不能超過k。

因此先求出 t = num1 - k * num2;

接著判斷 0 < t, k <= t，快速判斷一個數字是由幾個2的冪次方組合的方法，就是將數字轉換成2進制，數他有幾個1(ex 7 = bin(111), 4+2+1)，c++甚至有提供函式
```
__builtin_popcountll();
```
可以數2進制有幾個1，只要符合條件回傳答案即可

---


## C++ 實作
```cpp
class Solution {
public:
    int makeTheIntegerZero(long long int num1, long long int num2) {
        for(int i = 0; i <= 60; i++){
            long long t = num1 - i * num2;
            if( t < 0) continue;
            unsigned long long u = (unsigned long long) t;
            if(__builtin_popcountll(u) <= i && i <= t )
                return (int)i;
        }
        return -1;
    }
};
```
---

## 關鍵點