当前位置：首页 > article >正文

LeetCode每日一题3226---使两个整数相等的位更改次数

article 2024/11/5 2:24:15

一、题目描述

给你两个正整数 n 和 k。

你可以选择 n 的二进制表示中任意一个值为 1 的位，并将其改为 0。

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

示例 1：

输入： n = 13, k = 4

输出： 2

解释：
最初，n 和 k 的二进制表示分别为 n = (1101)2 和 k = (0100)2，

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

示例 2：

输入： n = 21, k = 21

输出： 0

解释：
n 和 k 已经相等，因此不需要更改。

示例 3：

输入： n = 14, k = 13

输出： -1

解释：
无法使 n 等于 k。

提示：

1 <= n, k <= 106

二、解题思路

从集合的角度理解，k 必须是 n 的子集。如果不是，返回 −1。怎么用位运算判断，见上面的文章链接。

如果 k 是 n 的子集，答案为从 n 中去掉 k 后的集合大小，即 n⊕k 的二进制中的 1 的个数。

我们需要将整数 n 的二进制表示变成 k，并且只能将 n 中的 1 改为 0。
如果 k 的二进制表示中有比 n 中的 1 位置多的 1，则无法实现，将返回 -1。
否则，统计 n 和 k 中 1 的不同位置，计算最少的更改次数。
步骤：
使用按位与（&）和按位异或（^）来判断 n 和 k 的差异。
遍历 n 和 k 的二进制位，统计需要从 1 改为 0 的次数。
如果 k 的某一位是 1，而 n 的对应位是 0，则返回 -1，因为无法实现该转换。

三、代码

class Solution {
public:
    int minChanges(int n, int k) {
        int ret = 0;
        for (;n || k; n >>= 1, k >>= 1){
            if (n % 2 && !(k % 2)){
                ret++;
            }
            else if (!(n % 2) && k % 2){
                return -1;
            }
        }
        return ret;
    }
};