Guess the Number Using Bitwise Questions I

Guess the Number Using Bitwise Questions I - Problem

There is a number n that you have to find. There is also a pre-defined API int commonSetBits(int num), which returns the number of bits where both n and num are 1 in that position of their binary representation.

In other words, it returns the number of set bits in n & num, where & is the bitwise AND operator.

Return the number n.

Input & Output

Example 1 — Target is 13

$ Input: n = 13 (binary: 1101)

› Output: 13

💡 Note: Test powers of 2: commonSetBits(1)=1, commonSetBits(2)=0, commonSetBits(4)=1, commonSetBits(8)=1. This gives us bits 0,2,3 are set, so n = 1+4+8 = 13

Example 2 — Target is 7

$ Input: n = 7 (binary: 111)

› Output: 7

💡 Note: Test: commonSetBits(1)=1, commonSetBits(2)=1, commonSetBits(4)=1, commonSetBits(8)=0. Bits 0,1,2 are set, so n = 1+2+4 = 7

Example 3 — Target is 1

$ Input: n = 1 (binary: 1)

› Output: 1

💡 Note: Test: commonSetBits(1)=1, commonSetBits(2)=0, commonSetBits(4)=0. Only bit 0 is set, so n = 1

Constraints

1 ≤ n ≤ 2³⁰
You can call the API at most 30 times

Visualization

Tap to expand

Understanding the Visualization

Unknown Target

We need to find n, only knowing commonSetBits API

Strategic Testing

Test with powers of 2 to isolate each bit

Reconstruct Number

Combine detected bits to form the answer

Key Takeaway

🎯 Key Insight: Each bit can be detected independently by testing with its corresponding power of 2

Asked in

G Google 15 M Microsoft 12 a Amazon 8

This problem requires bit manipulation to efficiently discover an unknown number using a limited API. The key insight is to test each bit position independently using powers of 2 (1, 2, 4, 8, 16...). Best approach uses bit-by-bit detection with Time: O(log n), Space: O(1).

Common Approaches

Approach	Time	Space	Notes
✓ Bit Manipulation - Build Number Bit by Bit	O(log n)	O(1)	Test each bit position independently using powers of 2
Optimized Bit Detection	O(log log n)	O(1)	Smart bit detection using binary patterns and fewer API calls
Brute Force - Test All Numbers	O(n)	O(1)	Try every possible number until we find one that matches all API responses

Bit Manipulation - Build Number Bit by Bit — Algorithm Steps

Initialize result = 0
For each bit position i (0 to 30)
Test with 2^i using commonSetBits API
If response > 0, set bit i in result

Visualization

Tap to expand

Step-by-Step Walkthrough

Test Powers of 2

Try 1, 2, 4, 8, 16... (2^0, 2^1, 2^2...)

Check API Response

If commonSetBits(2^i) > 0, bit i is set

Build Result

Combine all set bits to form the answer

Code -

solution.c — C

#include <stdio.h>

int target; // For simulation

int popcount(int x) {
    int count = 0;
    while (x) {
        count += x & 1;
        x >>= 1;
    }
    return count;
}

int commonSetBits(int num) {
    return popcount(target & num);
}

int solution(int n) {
    target = n; // For simulation
    
    int result = 0;
    
    // Test each bit position from 0 to 30
    for (int i = 0; i < 31; i++) {
        int powerOf2 = 1 << i; // This is 2^i
        
        // Ask API: how many bits do n and 2^i have in common?
        int commonBits = commonSetBits(powerOf2);
        
        // If there's a common bit, then bit i is set in n
        if (commonBits > 0) {
            result |= powerOf2; // Set bit i in result
        }
    }
    
    return result;
}

int main() {
    int n;
    scanf("%d", &n);
    printf("%d\n", solution(n));
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(log n)

Test at most 31 bit positions (log₂ of max 32-bit integer)

⚡ Linearithmic

Space Complexity

O(1)

Only use a few variables to track result and bit position

✓ Linear Space

12.3K Views

Medium Frequency

~15 min Avg. Time

456 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Bit Manipulation - Build Number Bit by Bit — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler