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 II

Number: 3401

Difficulty: Medium

Paid? Yes

Companies: N/A

Problem Description

There is a hidden 30‐bit number n (i.e. 0 ≤ n ≤ 2^30 – 1). You have access to an API commonBits(num) that works in two steps. First it calculates and returns the number of bit positions (among the 30 least–significant bits) where n and num have the same bit (i.e. both 0 or both 1). Then it updates n by replacing it with n XOR num. Although n changes with every call, your task is to determine the original (initial) value of n using as many queries as you like (provided your queries remain in range).

Key Insights

  • The API returns 30 minus the Hamming distance between n and the query number.
  • Every query permanently “flips” the bits of n at the positions where the query has a 1 bit.
  • Querying with 0 does not change n yet returns info (namely the count of zeros in n) since only positions where n has 0 will match.
  • By carefully performing queries and “undoing” the cumulative XOR effects, it is possible to “peel‐off” bit information one by one.
  • A strategy is to intentionally use “calibration” queries (using 0) to know the baseline number of 0 bits of the current state, and then make a query with a power of 2. The difference in the response tells you whether that specific bit in the current state was 0 or 1.
  • Finally, because every query flips n, the overall effect is that after a fixed sequence of queries the final value equals (original_n XOR cumulative_query_mask). Knowing the cumulative mask lets us recover the original n.

Space and Time Complexity

Time Complexity: O(30) = O(1) per test case (we make ~60 queries at most)
Space Complexity: O(1)

Solution

The idea is to “probe” each bit from the most significant bit (bit 29) down to the least significant one. We first make a query with 0 to determine the baseline number of positions where n has a 0; call this baseline. Then, for each bit position i, we:

  1. Query with 0 to “read” the current state’s zero–count (this query does not change n).
  2. Query with (1 << i) and observe the response. In the current state there are two possibilities:
    • If the i–th bit is 1, flipping it (by XOR with 1<<i) will turn it to 0 so that the response increases by 1 relative to the baseline (because that position now “mismatches” the 0 in the query would have contributed a 1 if it were already 1).
    • If the i–th bit is 0, flipping it makes it 1 causing one fewer matched bit (a decrease by 1).
  3. Based on the comparison between the two responses (before and after the flip) we determine the bit value in the current state.
  4. Although updating n with each query changes the internal state, note that the overall effect of a sequence of queries Q is that the final state equals original_n XOR Q. As we record the “flip” (i.e. the power–of–2 mask we used for each bit) in a cumulative variable, we can “undo” the overall effect at the very end.
  5. Finally, after processing all 30 bits, we perform one final query with 0 to read the final state and then recover the original n by XOR–ing out the cumulative query mask.

We use simple bit–manipulation and careful simulation of the state evolution. The main “gotcha” is that every query (except with 0) flips some bits; therefore we must keep track of the cumulative XOR (the aggregate of all non–zero queries), so that once we know the final state, we can recover the original n.

Data structures used: a couple of integer variables to record the cumulative mask and temporary results. The algorithmic approach is greedy bit by bit determination using differences in the API’s returned “common bits” count.

Code Solutions

Below are line–by–line commented solutions in Python, JavaScript, C++ and Java. (The interactive function commonBits(num) is assumed to be provided by the judge.)

# Function to simulate the query (interactive API call)
def query(num):
    # In the interactive problem, this function would perform an API call.
    # Here, we assume it is available and returns an integer.
    return commonBits(num)

def findInitialNumber():
    # Initialize cumulative_mask to keep track of all queries that flip bits.
    cumulative_mask = 0

    # First, query with 0 to get baseline info; this does not change n.
    baseline = query(0)
    # baseline equals the number of positions where the current n has bit 0 (because 0==0)

    # We will determine each bit in the current state (which is evolving)
    # Note: current state = original_n XOR cumulative_mask.
    # We will use an array to record the deduced bits from MSB (bit 29) to LSB (bit 0)
    deduced_bits = 0

    # Process bits from 29 down to 0.
    for i in range(29, -1, -1):
        # Query with 0 to read the current state's number of zero bits (calibration).
        current_zero_count = query(0)

        # Query with (1 << i) to flip only the i-th bit.
        response = query(1 << i)
        # When query(x) is called, it returns the number of bits (in the current state)
        # that are same as in x, and then it sets current state = current state XOR x.

        # Let current state be 's' (unknown to us); let cnt0 = number of indices j where s[j]==0.
        # Note that a query with (1 << i) (which has 1 at position i and 0 elsewhere)
        # contributes:
        # for j != i: count 1 if s[j]==0 (same as query bit 0) -> overall contributes (cnt0 - (s[i]==0? 1:0))
        # for j == i: count 1 if s[i]==1 (since query bit is 1) else 0.
        # Thus, if s[i]==1, response should equal: 1 + (cnt0) = cnt0 + 1.
        # But if s[i]==0, response should equal: 0 + (cnt0-1) = cnt0 - 1.
        #
        # Therefore:
        # If response equals current_zero_count + 1, then bit i in current state was 1.
        # If response equals current_zero_count - 1, then bit i in current state was 0.
        if response == current_zero_count + 1:
            # The current state's i-th bit is 1.
            deduced_bits |= (1 << i)
        # Otherwise, it must be 0 and deduced_bits already has 0 at that bit.
        #
        # Note: The query with (1 << i) has updated the state,
        # so we move on with the next bit.
        #
        # Also, update cumulative_mask with the query that flipped the i-th bit.
        cumulative_mask ^= (1 << i)

    # After processing all bits, we read one final time without altering state.
    final_state = query(0)  # using query with 0 returns info but does not change state
    #
    # The important invariant: current_state = original_n XOR cumulative_mask.
    # We cannot read original_n directly, but based on our queries, we know cumulative_mask.
    # However, note that final_state here is not the bit–representation but the count of zeros.
    # In an interactive environment, one would use the logic (or additional queries)
    # to eventually output the final guess. For our explanation, assume there is a way
    # to obtain the current state's bit representation (e.g. by combining the recovered bits).
    #
    # In our simulation, deduced_bits holds the aggregated bits extracted from the evolving state.
    # Given that each query flipped exactly the bits as recorded in cumulative_mask,
    # the relation is: deduced_bits = (original_n XOR cumulative_mask).
    # Hence, to recover original_n:
    original_n = deduced_bits ^ cumulative_mask

    return original_n

# Example usage:
# ans = findInitialNumber()
# print(ans)
← Back to All Questions