Skip to content

Latest commit

 

History

History
153 lines (115 loc) · 4.03 KB

README_EN.md

File metadata and controls

153 lines (115 loc) · 4.03 KB
comments difficulty edit_url tags
true
Medium
Bit Manipulation
Interactive

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

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

Python3

# 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

Java

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

C++

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

Go

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