We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Guess the Number Using Bitwise Questions I

Number: 3370

Difficulty: Medium

Paid? Yes

Companies: N/A

Problem Description

You have a hidden number n (1 <= n <= 2^30 - 1). An API commonSetBits(num) is provided that returns the number of common set bits between n and num (i.e. the count of 1 bits in n & num). Your task is to determine the value of n by making calls to the API.

Key Insights

  • Use the API to individually check if a specific bit is set in n.
  • Since n is less than 2^30, only 30 bits need to be examined.
  • Querying with a number containing a single set bit (like 1<<i) will return 1 if that bit is set in n, and 0 otherwise.
  • Aggregate the bits to reconstruct the number n.

Space and Time Complexity

Time Complexity: O(30) per query, which is constant time relative to the input size. Space Complexity: O(1) since only a constant amount of extra space is used.

Solution

The solution uses a bit-by-bit reconstruction approach. For each bit position from 0 to 29, we send a query with a number having only that bit set. The API commonSetBits returns 1 if that particular bit is set in n (because the bit holds a value of 1 in both n and the query). If the response is 1, we set that bit in our result. This way, by iterating through all 30 bits, we can construct the entire number n. The key idea is that by isolating every bit using a "mask" (1 << bit), we turn the problem into 30 independent bit checks.

Code Solutions

# Define the function that uses the provided API commonSetBits to determine n.
def guessNumber():
    result = 0
    # Since n is at most 2^30 - 1, we only need to check 30 bits.
    for bit in range(30):
        # Create a mask with only the bit-th bit set.
        mask = 1 << bit
        # Call the provided API commonSetBits with the mask.
        # If the returned count is 1, it means the bit exists in n.
        if commonSetBits(mask) == 1:
            result |= mask  # Set the bit in the result.
    return result

# Example usage (the API commonSetBits would be provided externally)
# print(guessNumber())
← Back to All Questions