What is the main strategy to solve 'Number of Bit Changes to Make Two Integers Equal'?

The main strategy is to compare the binary representations of the two integers, using bitwise operations like XOR to identify the positions that need to be changed.

What happens if it is impossible to make the integers equal?

If it is impossible to change n into k (when k has bits set to 1 where n has 0s), the answer should be -1.

How do XOR operations help in solving this problem?

XOR helps by efficiently identifying the positions where the bits differ between n and k, allowing you to count how many bits need to be flipped.

What are the time and space complexities of the solution?

The time complexity is O(log n) due to the binary representation and XOR operations. The space complexity is O(1) as it only requires a fixed amount of extra space.

Can this problem be extended to multiple integers?

Yes, one variant could involve extending the problem to multiple integers, where you calculate the minimum number of bit changes required to make all integers equal.

#3226

Easy

auto_awesome位运算·操作·driven·solution·strategy

LeetCode 题解工作台

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

给你两个正整数 n 和 k 。你可以选择 n 的二进制表示中任意一个值为 1 的位，并将其改为 0。返回使得 n 等于 k 所需要的更改次数。如果无法实现，返回 -1。示例 1：输入： n = 13, k = 4 输出： 2 解释：最初， n 和 k 的二进制表示分别为 n = (11…

位运算

题目描述

给你两个正整数 n 和 k。

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

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

示例 1：

输入： n = 13, k = 4

输出： 2

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

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

示例 2：

输入： n = 21, k = 21

输出： 0

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

示例 3：

输入： n = 14, k = 13

输出： -1

解释：
无法使 n 等于 k。

提示：

1 <= n, k <= 10⁶

lightbulb

解题思路

方法一：位运算

如果 $n$ 和 $k$ 的按位与结果不等于 $k$ ，说明 $k$ 存在某一位为 $1$ ，而 $n$ 对应的位为 $0$ ，此时无法通过改变 $n$ 的某一位使得 $n$ 等于 $k$ ，返回 $-1$ ；否则，我们统计 $n \oplus k$ 的二进制表示中 $1$ 的个数即可。

时间复杂度 $O(\log n)$ ，空间复杂度 $O(1)$ 。

1

2

3

4

class Solution:
    def minChanges(self, n: int, k: int) -> int:
        return -1 if n & k != k else (n ^ k).bit_count()

speed

复杂度分析

指标	值
时间	Depends on the final approach
空间	Depends on the final approach

psychology

面试官常问的追问

外企场景

question_mark
Look for candidates who understand bit manipulation concepts like XOR and bit shifts.
question_mark
Evaluate how well the candidate can translate bitwise operations into a solution strategy.
question_mark
Assess the candidate’s understanding of edge cases, like impossibilities in the transformation of n to k.

warning

常见陷阱

外企场景

error
Forgetting that bits in k set to 1 when corresponding bits in n are 0 make the problem unsolvable.
error
Incorrectly assuming that the binary representation comparison only requires a one-to-one match, overlooking the transformation rules.
error
Misunderstanding the XOR operation and not using it to efficiently detect bit differences.

swap_horiz

进阶变体

外企场景

arrow_right_alt
Extend this problem to include multiple integers and find the minimum number of changes to make all integers equal.
arrow_right_alt
Consider a variant where bits can be flipped both ways (0 to 1 and 1 to 0) to make n equal to k.
arrow_right_alt
Introduce a time limit constraint for large inputs and test the efficiency of the solution.

help

常见问题

外企场景

继续练习

#3211 生成不含相邻零的二进制字符串 #3209 子数组按位与值为 K 的数目 #3191 使二进制数组全部等于 1 的最少操作次数 I