Question

3064. 使用按位查询猜测数字 I

English Version

题目描述

你需要找到一个数字 n。

这里有一个预定义的 API int commonSetBits(int num)，它返回 n 和 num 在二进制表示的同一位置上都是 1 的位数。换句话说，它返回 n & num 的 设置位 数量，其中 & 是按位 AND 运算符。

返回数字 n。

 

示例 1：

输入：n = 31

输出：31

解释：能够证明使用给定的 API 找到 31 是可能的。

示例 2：

输入：n = 33

输出：33

解释：能够证明使用给定的 API 找到 33 是可能的。

 

提示：

• 1 <= n <= 230 - 1
• 0 <= num <= 230 - 1
• 如果你查询的 num 超出了给定的范围，输出就不可靠。

解法

方法一：枚举

我们可以枚举 $2$ 的幂次方，然后调用 commonSetBits 方法，如果返回值大于 $0$，则说明 $n$ 的二进制表示中的对应位是 $1$。

时间复杂度 $O(\log n)$，本题中 $n \le 2^{30}$。空间复杂度 $O(1)$。

# Definition of commonSetBits API.
# def commonSetBits(num: int) -> int:


class Solution:
  def findNumber(self) -> int:
    return sum(1 << i for i in range(32) if commonSetBits(1 << i))

/**
 * Definition of commonSetBits API (defined in the parent class Problem).
 * int commonSetBits(int num);
 */

public class Solution extends Problem {
  public int findNumber() {
    int n = 0;
    for (int i = 0; i < 32; ++i) {
      if (commonSetBits(1 << i) > 0) {
        n |= 1 << i;
      }
    }
    return n;
  }
}

/**
 * Definition of commonSetBits API.
 * int commonSetBits(int num);
 */

class Solution {
public:
  int findNumber() {
    int n = 0;
    for (int i = 0; i < 32; ++i) {
      if (commonSetBits(1 << i)) {
        n |= 1 << i;
      }
    }
    return n;
  }
};

/**
 * Definition of commonSetBits API.
 * func commonSetBits(num int) int;
 */

func findNumber() (n int) {
  for i := 0; i < 32; i++ {
    if commonSetBits(1<<i) > 0 {
      n |= 1 << i
    }
  }
  return
}

/**
 * Definition of commonSetBits API.
 * var commonSetBits = function(num: number): number {}
 */

function findNumber(): number {
  let n = 0;
  for (let i = 0; i < 32; ++i) {
    if (commonSetBits(1 << i)) {
      n |= 1 << i;
    }
  }
  return n;
}