Skip to content

3064. Guess the Number Using Bitwise Questions I πŸ”’

Description

There is a number n that you have to find.

There is also a pre-defined API int commonSetBits(int num), which returns the number of bits where both n and num are 1 in that position of their binary representation. In other words, it returns the number of set bits in n & num, where & is the bitwise AND operator.

Return the number n.

 

Example 1:

Input: n = 31

Output: 31

Explanation: It can be proven that it's possible to find 31 using the provided API.

Example 2:

Input: n = 33

Output: 33

Explanation: It can be proven that it's possible to find 33 using the provided API.

 

Constraints:

  • 1 <= n <= 230 - 1
  • 0 <= num <= 230 - 1
  • If you ask for some num out of the given range, the output wouldn't be reliable.

Solutions

Solution 1: Enumeration

Thinking

\(\texttt{commonSetBits}(x)\) is the number of \(1\)-bits shared by \(n\) and \(x\). \(n < 2^{30}\), so we may query bit by bit.

For \(x=2^i\) the result is nonzero iff bit \(i\) of \(n\) is set.

We try \(32\) powers of two and OR in every bit that answers true.

We can enumerate the powers of 2, and then call the commonSetBits method. If the return value is greater than 0, it means that the corresponding bit in the binary representation of n is 1.

The time complexity is \(O(\log n)\), where \(n \le 2^{30}\) in this problem. The space complexity is \(O(1)\).

1
2
3
4
5
6
7
# 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))

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
/**
 * 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;
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
/**
 * 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;
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
/**
 * 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
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
/**
 * 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;
}

Comments