3370. Smallest Number With All Set Bits

EasyBit ManipulationMath

Problem Description

You are given a positive number n.

Return the smallest number x greater than or equal to n, such that the binary representation of x contains only set bits.

Intuition

The key insight for this problem is understanding the properties of binary numbers composed entirely of set bits (ones). A binary number with all set bits has the form of all ones (e.g., 1, 11, 111, etc.), and corresponds to a decimal value of a power of two minus one (e.g., 2^1 - 1 = 1, 2^2 - 1 = 3, 2^3 - 1 = 7, etc.).

To find the smallest number x greater than or equal to n with this property, we can start with the smallest all-ones binary number and progressively consider each subsequent power of two by left-shifting a single 1 bit. The operation x << 1 effectively doubles x, adding another set bit to its binary form.

The approach involves maintaining a number x initialized to 1 and using a loop to keep shifting it left until x - 1 is greater than or equal to n. Once x - 1 meets this condition, it represents the smallest binary number composed entirely of set bits that is not smaller than n.

Learn more about Math patterns.

Solution Approach

The solution utilizes bit manipulation to achieve the desired result efficiently. Here's a step-by-step breakdown of the algorithm:

Initialization: Start with x = 1. This represents the smallest number with only one set bit, which is 1 in binary.
Loop Condition: While x - 1 is less than n, keep increasing x. The condition x - 1 < n ensures that we continue the loop until we find a number x such that x - 1 is greater than or equal to n.
Left Shift Operation: Inside the loop, perform the operation x <<= 1. This operation doubles the value of x by shifting its binary representation one bit to the left, which adds an additional set bit to the number. For example, if x is 1 (binary 1), after left-shifting, it becomes 10 (binary 2), then 100 (binary 4), and so on.
Final Output: The loop repeats this doubling process until x - 1 becomes greater than or equal to n. At this point, x - 1 is the smallest number with all set bits in its binary representation, satisfying the problem's requirement.

This approach efficiently finds the smallest number with all set bits that is not less than n using basic bit manipulation, specifically the left shift operation, which achieves a logarithmic complexity relative to the number of bits used to represent n.

Ready to land your dream job?

Unlock your dream job with a 2-minute evaluator for a personalized learning plan!

Start Evaluator

Example Walkthrough

Let's illustrate the solution with a small example:

Suppose we are given n = 6. We need to find the smallest number x such that x >= 6 and the binary representation of x contains only set bits (e.g., 111, 1111, etc.).

Initialization: Start with x = 1. Initially, x - 1 = 0, which is less than 6.
First Iteration:
- Perform x <<= 1, which shifts x left by one bit.
- Originally x was 1 (binary 01). After the shift, x becomes 2 (binary 10).
- Now, x - 1 = 2 - 1 = 1, still less than 6.
Second Iteration:
- Again perform x <<= 1.
- x is now 2 (binary 10). After the shift, it becomes 4 (binary 100).
- Now, x - 1 = 4 - 1 = 3, still less than 6.
Third Iteration:
- Perform x <<= 1 again.
- x is 4 (binary 100). After the shift, it becomes 8 (binary 1000).
- Now, x - 1 = 8 - 1 = 7, which is greater than or equal to 6.

Since x - 1 = 7, which satisfies the condition x - 1 >= n, we stop here. The smallest number x where x - 1 equals 7 is 7 in decimal, represented as 111 in binary. This is the smallest number with all binary set bits not less than n = 6.

Solution Implementation

1class Solution:
2    def smallestNumber(self, n: int) -> int:
3        # Initialize the variable x to 1, which will be used to find the smallest power of two minus one
4        x = 1
5      
6        # Loop until x - 1 is less than the given number n
7        while x - 1 < n:
8            # Left shift x by one bit (equivalent to multiplying by 2)
9            x <<= 1
10      
11        # Return x - 1 as it represents the smallest number greater than or equal to n
12        return x - 1
13

1class Solution {
2    public int smallestNumber(int n) {
3        // Initialize x to 1
4        int x = 1;
5      
6        // Shift x to the left (multiply by 2) until x - 1 is greater than or equal to n
7        while (x - 1 < n) {
8            x <<= 1; // Equivalent to x = x * 2
9        }
10      
11        // Return x - 1, which is the smallest number greater than or equal to n
12        return x - 1;
13    }
14}
15

1class Solution {
2public:
3    int smallestNumber(int n) {
4        int powerOfTwo = 1; // Initialize variable to represent powers of 2
5
6        // Loop until powerOfTwo - 1 is at least n
7        while (powerOfTwo - 1 < n) {
8            powerOfTwo <<= 1; // Left shift powerOfTwo by one (equivalent to multiplying by 2)
9        }
10
11        // Return the value which is one less than the next power of 2 that exceeds or equals n
12        return powerOfTwo - 1;
13    }
14};
15

1function smallestNumber(n: number): number {
2    // Start with x initialized to 1
3    let x = 1;
4  
5    // Multiply x by 2 in each iteration until x - 1 is no longer less than n
6    while (x - 1 < n) {
7        x <<= 1;  // Left shift x by 1, which is equivalent to multiplying by 2
8    }
9  
10    // Return the largest power of 2 minus 1 that is greater than or equal to n
11    return x - 1;
12}
13

Time and Space Complexity

The time complexity of the code is O(log n), as the loop iterates by shifting x left until x - 1 is not less than n, which effectively means the loop runs a number of times proportional to the number of bits needed to represent n.

The space complexity of the code is O(1), since the method uses a constant amount of extra space, specifically the integer x, regardless of the input size n.

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

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

Question 1 out of 10

What data structure does Breadth-first search typically uses to store intermediate states?

Stack

Queue

Tree

Linked List

I don’t know