Guess the Number Using Bitwise Questions I Solution in Java

Quick Links

Problem Description

So, you think you can guess a number? Welcome to the world of “Guess the Number Using Bitwise Questions!” where your guessing skills are put to the ultimate test. Imagine you’re at a party, and someone challenges you to guess their secret number between 1 and 1,073,741,823. Instead, you can only ask questions about the bits of the number.

In this problem, you have a function commonSetBits(int num) that tells you how many bits are set in the number you provide. Your task is to find the number that has exactly one bit set.

Code Solution


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

public class Solution extends Problem {
  public int findNumber() {
    final int kMaxBit = 30;
    int ans = 0;
    for (int i = 0; i <= kMaxBit; ++i)
      if (commonSetBits(1 << i) == 1)
        ans |= 1 << i;
    return ans;
  }
}

Approach

The approach here is quite straightforward. The code iterates through all possible bit positions (from 0 to 30) and checks if the number formed by shifting 1 to the left by i has exactly one bit set using the commonSetBits function. If it does, that bit is included in the final answer.

Time and Space Complexity

Complexity Type	Complexity
Time Complexity	O(1) - The loop runs a constant number of times (31 iterations).
Space Complexity	O(1) - We are using a fixed amount of space regardless of the input size.

Real-World Example

Imagine you’re at a carnival, and there’s a game where you have to guess which balloon is filled with helium. You can only ask if a balloon is filled with helium or not. Each time you ask, you narrow down your options until you find the right one. This problem is similar; you’re using bitwise operations to narrow down the possibilities until you find the number with exactly one bit set.