Skip to content

3094. Guess the Number Using Bitwise Questions II πŸ”’

Description

There is a number n between 0 and 230 - 1 (both inclusive) that you have to find.

There is a pre-defined API int commonBits(int num) that helps you with your mission. But here is the challenge, every time you call this function, n changes in some way. But keep in mind, that you have to find the initial value of n.

commonBits(int num) acts as follows:

  • Calculate count which is the number of bits where both n and num have the same value in that position of their binary representation.
  • n = n XOR num
  • Return count.

Return the number n.

Note: In this world, all numbers are between 0 and 230 - 1 (both inclusive), thus for counting common bits, we see only the first 30 bits of those numbers.

 

Constraints:

  • 0 <= 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: Bit Manipulation

Thinking

\(\texttt{commonBits}(x)\) XORs \(n\) with \(x\) and then returns the number of shared \(1\)-bits. Each query permanently changes \(n\).

Querying the same \(x\) twice restores \(n\). Comparing the two answers tells whether that bit was originally \(1\): a decrease on the second call means it started as \(1\).

For every bit we query \(1\ll i\) twice and set the bit when the first count is larger.

Based on the problem description, we observe that:

  • If we call the commonBits function twice with the same number, the value of \(n\) will not change.
  • If we call commonBits(1 << i), the \(i\)-th bit of \(n\) will be flipped, i.e., if the \(i\)-th bit of \(n\) is \(1\), it will become \(0\) after the call, and vice versa.

Therefore, for each bit \(i\), we can call commonBits(1 << i) twice, denoted as count1 and count2 respectively. If count1 > count2, it means the \(i\)-th bit of \(n\) is \(1\), otherwise it is \(0\).

The time complexity is \(O(\log n)\), and the space complexity is \(O(1)\).

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
# Definition of commonBits API.
# def commonBits(num: int) -> int:


class Solution:
    def findNumber(self) -> int:
        n = 0
        for i in range(32):
            count1 = commonBits(1 << i)
            count2 = commonBits(1 << i)
            if count1 > count2:
                n |= 1 << i
        return n

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
/**
 * Definition of commonBits API (defined in the parent class Problem).
 * int commonBits(int num);
 */

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

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
/**
 * Definition of commonBits API.
 * int commonBits(int num);
 */

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

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
/**
 * Definition of commonBits API.
 * func commonBits(num int) int;
 */

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

Comments