. - 力扣（LeetCode）

题目

给你两个正整数 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最后一位，进行比较

• 如果last_n == last_k， 则不需要修改，继续遍历
• 如果lask_n != last_k:
  • 如果last_n == 1, last_k == 0, 则需要改变操作，操作数+1
  • 如果last_n == 0, last_k == 1, 则无法通过指定操作使n变成k, 直接返回-1

class Solution:
    def minChanges(self, n: int, k: int) -> int:
        if n < k:
            return -1
        if n == k:
            return 0
        mod = 0
        while k > 0 or n > 0:
            last_n = n & 1 # 取n的最后一位
            last_k = k & 1 # 取k的最后一位
            n = n >> 1
            k = k >> 1
            if last_n == last_k:
                print(last_n, last_k, n, k, mod)
                continue
            elif last_k == 1:
                return - 1
            else:
                mod += 1 
            print(last_n, last_k, n, k, mod)
        return mod
            

        
        

分析复杂度

• 时间复杂度是n和k位数的最大值： 

• 空间复杂度是

2. 位操作

如果把n和k的二进制为1的位分别看做一个集合，那么k应该是n的一个子集。

1. 按位或操作，如果操作结果等于k，则n可以通过修改某些位置上1为0得到k；反之则不能，直接返回-1.

2. 已知n可以通过修改某些位置上1为0得到k，接下来进行异或操作（n和k不同的位为1，即需要修改的位为1），统计操作结果中1的位数即可

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

分析复杂度

• 时间复杂度 O(1)
• 空间复杂度 O(1)