6471. 得到整数零需要执行的最少操作数 (opens new window)

1.枚举+模拟

分析：将题目转化为num1-num2后，剩余的数能不能由多个2的整数次幂相加。而这里“多个”又该如何控制？

• num1-num2*1的结果，只能由1个2的整数次幂相加
• num1-num2*2的结果，只能由2个2的整数次幂相加
• ...

而对于两个2的整数次幂来说，它们相加结果的二进制表示有两种情况：

• 二进制位为1的位数为1，当前仅当存在二进制”进位“时为1，比如4+4=8---1000
• 二进制位为1的位数为2，比如4+2=6---0110

而进位的最极端的情况就是全部都是通过1相加不断进位得到。令sum=num1-num2*level，则sum能否由level个2的整数次方幂相加得到，就等价于不等式是否满足cal(sum)<=level<=sum。下界是cal(sum)计算纸面上的sum的二进制表示1的个数，上界就是上述极端情况。

class Solution {
    public int makeTheIntegerZero(int num1, int num2) {
        if(num2>=num1) return -1;
        long sum=0,level=1;
        while(true){
            sum=num1-num2*level;
            if(sum<=0) return -1;
            if(cal(sum)<=level&&level<=sum) return (int)level;
            level++;
        }
    }
    public int cal(long a){
        int res=0;
        while(a!=0){
            if(a%2==1) res++;
            a=a>>1;
        }
        return res;
    }
}