You are given two positive integers n and k.
You can choose any bit in the binary representation of n that is equal to 1 and change it to 0.
Return the number of changes needed to make n equal to k. If it is impossible, return -1.
Example 1:
Input: n = 13, k = 4
Output: 2
Explanation:
Initially, the binary representations of n and k are n = (1101)2 and k = (0100)2.
We can change the first and fourth bits of n. The resulting integer is n = (0100)2 = k.
Example 2:
Input: n = 21, k = 21
Output: 0
Explanation:
n and k are already equal, so no changes are needed.
Example 3:
Input: n = 14, k = 13
Output: -1
Explanation:
It is not possible to make n equal to k.
Constraints:
1 <= n, k <= 106
使两个整数相等的位更改次数。
给你两个正整数 n 和 k。你可以选择 n 的 二进制表示 中任意一个值为 1 的位,并将其改为 0。
返回使得 n 等于 k 所需要的更改次数。如果无法实现,返回 -1。
思路
这是一道位运算的问题。首先注意,这道题里我们只能改 n 的某个 digit,不能改 k 中的 digit;而且我们只能把 1 改成 0,不能把 0 改成 1。
那么判断是否能改和怎么改呢?因为不能改 k 中的任何 digit,所以我们可以计算一下 n & k
,如果n & k != k
,则说明 n 中有一些位置上存在 0,而我们是不能改动 0 的,这种 case 我们就直接返回 -1。如果n & k == k
,起码说明我们可以改。此时我们可以用各种语言自带的 API 统计一下 n 和 k 分别包含几个 1,然后返回他们的差值即可。
或者我们也可以看 n | k
是否等于 n,如果等于 n,则说明 k 里面不存在多余的 1。通过这个方式我们也可以判断是否可以改动。
复杂度
时间O(1)
空间O(1)
代码
Java实现
class Solution {
public int minChanges(int n, int k) {
return (n & k) != k ? -1 : Integer.bitCount(n ^ k);
}
}
class Solution {
public int minChanges(int n, int k) {
return (n | k) != n ? -1 : Integer.bitCount(n ^ k);
}
}
标签:Integers,digit,return,int,Make,3226,equal,Output,Example
From: https://www.cnblogs.com/cnoodle/p/18521563