3064. Guess the Number Using Bitwise Questions I

MediumBit ManipulationInteractive
Leetcode Link

Problem Description

In this problem, we have to find a certain number n using an API called commonSetBits. This API takes an integer num as its input and returns the number of set bits (1 bits) at the same positions in both n and num. The bit positions are counted from the least significant bit, which is position 0. The API is essentially calculating the number of 1 bits in the result of n AND num.

The task is to determine n exactly.

To clarify with an example: if n is 5, which has a binary representation of 101, and we call commonSetBits(1) which is 001 in binary, it will return 1, because they have one 1 in common at the 0th position. However, if we call commonSetBits(2) which is 010 in binary, it will return 0, because they don't have any 1 bits in common.

The constraints ensure that:

  • The unknown number n is between 1 and 2^30 - 1.
  • The input to commonSetBits, num, is between 0 and 2^30 - 1.
  • We cannot rely on the output of commonSetBits if the input num is outside the specified range.

Intuition

Given that we need to find the exact value of n and we have an API that tells us which bits are in common between n and any given num, the intuition is to call commonSetBits with inputs that help us isolate each bit of n.

The evident choice for such isolating calls would be powers of 2. Why? Because the binary representation of 2^i has a 1 at the ith position and 0 everywhere else. By calling commonSetBits(2^i) for every bit position from 0 to 31, we can check if that particular bit is set in n.

Then, we simply sum up all the powers of 2 where commonSetBits(2^i) returns a value indicating that the ith bit is set in n. Since we expect n to be a sum of powers of 2 (which is any integer's binary representation), this approach will yield us the original number n as required.

Not Sure What to Study? Take the 2-min Quiz to Find Your Missing Piece：

Which of the following problems can be solved with backtracking (select multiple)

Solution Approach

The solution involves a simple yet efficient approach which is a straightforward implementation of the intuition we've discussed.

Since we know the number of bits in n is limited (up to 32 for an integer within the constraint of 2^30 - 1), we can iteratively check each bit position to see whether it is set in n. We do this by using the power of 2 for each bit position as input to the commonSetBits API: 2^0, 2^1, 2^2, ..., 2^31.

The provided code in the solution uses list comprehension to create a list of such powers of 2 only where the corresponding bit is set in n, determined by whether commonSetBits(1 << i) is greater than 0.

Here is the breakdown:

  • For each bit position i from 0 to 31:
    • Calculate 1 << i, which is a number with only the ith bit set (indicating 2^i).
    • Call commonSetBits(1 << i) and check if the result is greater than 0. If yes, it means that the ith bit is also set in n since the common set bits are counted.
    • If the ith bit in n is set, include 1 << i in the sum.

Algorithmically, the list comprehension [1 << i for i in range(32) if commonSetBits(1 << i)] returns a list of all 2^i values that contribute to the final number n.

The sum() function then adds up all these individual powers of 2, which, when combined, reconstruct the original number n.

This solution is effective since it requires only 32 calls to commonSetBits (one for each bit) and uses no additional data structures. Overall, the code's time complexity is O(32), which is effectively O(1) since it's a constant time operation, and the space complexity is also O(1) as there are no data structures using space proportional to the size of the input.

Here's a visualization of the algorithm for a number n's binary representation 1101 (13 in decimal):

1Bit position:  3210
2n:            1101
32^0 (1):      0001 (API returns 1, bit is set)
42^1 (2):      0010 (API returns 0, bit is not set)
52^2 (4):      0100 (API returns 1, bit is set)
62^3 (8):      1000 (API returns 1, bit is set)
7
8Resulting sum: 1 + 0 + 4 + 8 = 13 (which is n)

The use of bitwise shifts (<<) and checks for values greater than zero in the list comprehension makes the code both concise and optimal for the task at hand.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

Which type of traversal does breadth first search do?

Example Walkthrough

Let's go through a small example to illustrate the solution approach.

Suppose the unknown number n we're trying to find is 11, which is 1011 in binary. We want to use the commonSetBits API to identify the positions of the 1 bits in n.

Here's how we would proceed, step-by-step:

  1. We begin by checking if the least significant bit (LSB, bit position 0) is a 1 in n by calling commonSetBits(1), since 1 in binary is 0001. If n has a 1 at this position, the API will return 1.

    • commonSetBits(1) → returns 1 because both n (1011) and the input (0001) have a 1 at LSB.

  2. Next, we check bit position 1 by calling commonSetBits(2), which corresponds to binary 0010. The API will return 1 if n also has a 1 in this position.

    • commonSetBits(2) → returns 1 because n (1011) and the input (0010) both have a 1 at position 1.

  3. We then check bit position 2 with commonSetBits(4) (binary 0100). If n contains a 1 at this position, the API will return 1.

    • commonSetBits(4) → returns 0 indicating that position 2 in n is not set (n is 1011 and input is 0100).

  4. Moving on to bit position 3, we call commonSetBits(8), which is 1000 in binary. If n has a 1 bit here, the API will return 1.

    • commonSetBits(8) → returns 1 because both n (1011) and the input (1000) have a 1 at position 3.

Now that we have called the API with powers of 2 for each bit position up to the bit position 3, we have the following information:

  • The API returned 1 for inputs 1, 2, and 8.
  • The API returned 0 for input 4.

Using this information, we can sum up all powers of 2 corresponding to the API returning 1:

[ \text{Resulting sum} = 2^0 + 2^1 + 2^3 = 1 + 2 + 8 = 11 ]

The sum 11 is the original number n we aimed to find.

This example demonstrates how the solution uses powers of 2 to isolate each bit of the unknown number and correctly sum them to discover n with only a few calls to the API.

Solution Implementation

1# Let's assume there is a predefined API commonSetBits which, when given an integer,
2# returns the number of set bits (1's) common amongst all the elements upto 'num'.
3
4# Here we have a class 'Solution' with a method 'findNumber'
5class Solution:
6    def findNumber(self) -> int:
7        # Initialize 'result' to store sum of powers of 2 that meet the condition
8        result = 0
9        # Iterate over each bit position from 0 to 31 (for 32-bit integers)
10        for i in range(32):
11            # Use commonSetBits with a power of 2 (only that bit set to 1)
12            # Check if 'i'th bit is common amongst all numbers
13            # with the bit set using the API
14            if commonSetBits(1 << i):
15                # If common, add the corresponding power of 2 to the result
16                result += 1 << i
17        # Once done, return the sum which represents the number we are trying to find
18        return result
19
1/**
2 * The following class Solution is meant to find a number based on the set bits 
3 * that it has in common with other numbers through the `commonSetBits` API.
4 */
5public class Solution extends Problem {
6    /**
7     * This method determines the number that has common set bits with other numbers.
8     *
9     * @return the number which has the maximum number of common set bits with others.
10     */
11    public int findNumber() {
12        // Initialize the result variable that will store the number with common set bits.
13        int result = 0;
14      
15        // Iterate through each of the 32 bits of an integer.
16        for (int i = 0; i < 32; ++i) {
17            // Create a bitmask with only the i-th bit set.
18            int bitmask = 1 << i;
19          
20            // Use the commonSetBits API to check if the current bit is set in the common number.
21            if (commonSetBits(bitmask) > 0) {
22                // If the i-th bit is common, include it in the result using bitwise OR.
23                result |= bitmask;
24            }
25        }
26      
27        // Return the number with all common set bits combined.
28        return result;
29    }
30}
31
1/**
2 * Forward declaration of the API.
3 * int commonSetBits(int num);
4 * The API is used to check how many bits set (to 1) in the input 'num' are common 
5 * with a specific unknown number.
6 * 
7 * @param num The number to test against the unknown number.
8 * @return The number of common bits set to 1 in the input 'num' and the unknown number.
9 */
10
11class Solution {
12public:
13    /**
14     * Finds the unknown number with which the `commonSetBits` API compares.
15     * 
16     * @return The unknown number that shares the common set bits with the input 
17     *         to the `commonSetBits` API.
18     */
19    int findNumber() {
20        int result = 0; // Initialize result to 0.
21
22        // Loop through all bit positions from 0 to 31 (assuming 32-bit integer)
23        for (int i = 0; i < 32; ++i) {
24            // Check if bit at position 'i' is set in the unknown number by
25            // passing a number with only the 'i'th bit set to the API.
26            int bitMask = 1 << i; // Create a mask with only the 'i'th bit set.
27            if (commonSetBits(bitMask)) {
28                // If the 'i'th bit is common, set the 'i'th bit in the result.
29                result |= bitMask;
30            }
31        }
32
33        // Return the result which now represents the unknown number.
34        return result;
35    }
36};
37
1// Declaration of the commonSetBits API. This function takes a number and
2// returns the number of common set bits.
3declare function commonSetBits(num: number): number;
4
5// This function finds a number composed of bits that are commonly set
6// when using the `commonSetBits` function on powers of 2 up to 2^31.
7function findNumber(): number {
8    // Initialize the number to be returned.
9    let resultNumber = 0;
10  
11    // Iterate through all bits positions from 0 to 31 (32-bit number assumption).
12    for (let i = 0; i < 32; ++i) {
13        // Create a number with only the i-th bit set.
14        const bitMask = 1 << i;
15      
16        // Check if this bit is commonly set using the provided API function.
17        if (commonSetBits(bitMask)) {
18            // If so, set the i-th bit in the result number.
19            resultNumber |= bitMask;
20        }
21    }
22  
23    // Return the composed number containing all the common set bits.
24    return resultNumber;
25}
26
Not Sure What to Study? Take the 2-min Quiz：

Which of the following shows the order of node visit in a Breadth-first Search?

Time and Space Complexity

Time Complexity

The time complexity of the code is mainly determined by the for-loop that iterates over the range of 32, which stands for the number of bits in an integer data type in Python (assuming the standard 32-bit integer size). Inside the loop, the commonSetBits is called once for each bit position from 0 to 31.

Even though the loop runs 32 times which is a fixed number, the given reference mentions the time complexity as O(log n), where n <= 2^30. This could imply that the commonSetBits function itself has a time complexity of O(log n) due to potentially using operations that depend logarithmically on the value of the number passed to it. However, analyzing without the specifics of commonSetBits, the time complexity would seem to be O(1) since the loop runs a constant number of times.

Assuming that the commonSetBits function is indeed dependent on the number of bits set to 1 in a given number (which would not exceed 30 as per the given constraints and the context of the problem), the overall time complexity is O(log n) based on the problem's constraint that n <= 2^30.

Space Complexity

The space complexity of the code is O(1) since it does not allocate any additional space that grows with the size of the input. The only extra space used is for the variable i in the for-loop and the space needed for calculating the sum, which do not depend on the input size and are thus constant.

Learn more about how to find time and space complexity quickly using problem constraints.

Fast Track Your Learning with Our Quick Skills Quiz:

Which one best describes the time complexity of the following code?

1int factorial(int n) {
2  if (n < 0) {
3    return -1;
4  } else if (n == 0) {
5    return 1;
6  } else {
7    return n * factorial(n - 1);
8  }
9}

Recommended Readings

LeetCode Patterns - Top Patterns for Coding Interviews

Top Patterns to Conquer the Technical Coding Interview Should the written word bore you fear not A delightful video alternative awaits iframe width 560 height 315 src https www youtube com embed LW8Io6IPYHw title YouTube video player frameborder 0 allow accelerometer autoplay clipboard write encrypted media gyroscope picture in picture

Recursion Review

Recursion Recursion is one of the most important concepts in computer science Simply speaking recursion is the process of a function calling itself Using a real life analogy imagine a scenario where you invite your friends to lunch https algomonster s3 us east 2 amazonaws com recursion jpg You first

Runtime to Algo Cheat Sheet

Runtime Overview When learning about algorithms and data structures you'll frequently encounter the term time complexity This concept is fundamental in computer science and offers insights into how long an algorithm takes to complete given a certain input size What is Time Complexity Time complexity represents the amount of time

Got a question? Ask the Teaching Assistant anything you don't understand.

Still not clear? Ask in the Forum,  Discord or Submit the part you don't understand to our editors.

←
↑TA 👨‍🏫