Welcome to Subscribe On Youtube

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.

 

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:

  • 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

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)$.

  • /**
 * 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;
    }
}

  • /**
 * 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;
    }
};

  • # 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


  • /**
 * 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
}

All Problems

All Solutions