题目:
给你两个正整数 n
和 k
。你可以选择 n
的 二进制表示 中任意一个值为 1 的位,并将其改为 0。
返回使得 n
等于 k
所需要的更改次数。如果无法实现,返回 -1。
示例 1:
输入: n = 13, k = 4
输出: 2
解释:
最初,n
和 k
的二进制表示分别为 n = (1101)2
和 k = (0100)2
,
我们可以改变 n
的第一位和第四位。结果整数为 n = (**0**10**0**)2 = k
。
示例 2:
输入: n = 21, k = 21
输出: 0
解释:
n
和 k
已经相等,因此不需要更改。
示例 3:
输入: n = 14, k = 13
输出: -1
解释:
无法使 n
等于 k
。
提示:
1 <= n, k <= 106
思路:
从低到高,枚举k, n 的每一个二进制位ki, ni:
如果 ki == ni,跳过
如果 ki == 0 && ni == 1,需要进行一次操作
如果 ki == 1 && ni == 0,直接返回-1
k, n 向右移一位,直到有一个为 0
如果 k > 0,返回 -1
如果 n > 0,就右移 n,直到 n 为 0,同时记录有几个 1
代码:
class Solution {
public:
int minChanges(int n, int k) {
int ans = 0;
while (n && k) {
int flagn = n % 2, flagk = k % 2;
n >>= 1; k >>= 1;
if (flagn == flagk) {
continue;
} else if (flagk == 0 && flagn == 1) {
ans++;
} else return -1;
}
if (k) return -1;
while (n) {
if (n % 2) ans++;
n >>= 1;
}
return ans;
}
};