使两个整数相等的位更改次数

2024-11-02

题目:

给你两个正整数 nk。你可以选择 n二进制表示 中任意一个值为 1 的位,并将其改为 0。

返回使得 n 等于 k 所需要的更改次数。如果无法实现,返回 -1。

示例 1:

输入: n = 13, k = 4

输出: 2

解释: 最初,nk 的二进制表示分别为 n = (1101)2k = (0100)2

我们可以改变 n 的第一位和第四位。结果整数为 n = (**0**10**0**)2 = k

示例 2:

输入: n = 21, k = 21

输出: 0

解释: nk 已经相等,因此不需要更改。

示例 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;
    }
};