Back to Leetcode

Readme

Greedy/2749.Minimum-Operations-to-Make-the-Integer-Zero/Readme.md

latest747 B
Original Source

2749.Minimum-Operations-to-Make-the-Integer-Zero

本题就是寻找最小的操作次数k,使得num1-k*num2可以表示为k个2^i相加的形式,标记为(*)。

我们观察k个2^i相加,它有最小值就是k。所以如果num1-k*num2<k,那么必然无解。再观察k个2^i相加,它的最大值其实可以非常大,远超num1的数量范围。所以我们可以猜测,k个2^i相加,其实可以构造近乎任意的数字。事实上,这个通常情况下是成立的。只要num1-k*num2的二进制bit 1的个数count不多于k,那么总是可以构造成功。这是因为我们总可以用2^0+2^0=2^1的技巧,来消耗掉多余的2^i,使得构造出任何bit 1个数小于等于k的数字。