#3370

Easy

LeetCode Problem Workspace

Smallest Number With All Set Bits

Find the smallest number greater than or equal to n with all set bits in its binary representation.

Problem Statement

Given a positive integer n, return the smallest integer x such that x is greater than or equal to n, and its binary representation consists solely of set bits (1s). For example, for n = 5, the smallest number greater than or equal to 5 with all set bits is 7 (binary: 111).

The goal is to find an efficient way to compute this number, leveraging bit manipulation. The problem can be solved by determining the next power of two greater than or equal to n and subtracting one from it.

Examples

Example 1

Input: n = 5

Output: 7

The binary representation of 7 is "111" .

Example 2

Input: n = 10

Output: 15

The binary representation of 15 is "1111" .

Example 3

Input: n = 3

Output: 3

The binary representation of 3 is "11" .

Constraints

1 <= n <= 1000

Solution Approach

Finding the Next Power of Two

The first step is to compute the smallest power of two greater than or equal to n. This can be done by manipulating the bits of n. Once the next power of two is determined, subtracting one from it will result in the desired number.

Bitwise Shifting

Using bitwise shifting, we can efficiently determine the next power of two greater than or equal to n. Shift the bits of n to fill all lower bits with ones, and then subtract one to get the result.

Optimization for Larger n

When n is large, repeatedly shifting bits can be inefficient. Optimizing the bitwise operations, such as using the trick of finding the highest set bit and manipulating it directly, can improve performance.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

The time complexity depends on the bit manipulation approach used. The space complexity is O(1) since the solution only involves simple bitwise operations and does not require additional memory allocation.

What Interviewers Usually Probe

Candidate understands the concept of powers of two and bit manipulation.
Candidate applies bit manipulation to efficiently compute the answer.
Candidate avoids brute force approaches and seeks optimized solutions.

Common Pitfalls or Variants

Common pitfalls

Misunderstanding the binary representation of numbers with all set bits.
Using inefficient or brute force methods to calculate the result.
Overcomplicating the problem and missing simple bitwise solutions.

Follow-up variants

What if n is already a number with all set bits?
What if n is at the maximum limit (1000)?
What if n is a power of two, and no subtraction is needed?

FAQ

What is the best way to solve the Smallest Number With All Set Bits problem?

The most efficient solution is to find the next power of two greater than or equal to n, and then subtract 1 from it.

How do you calculate the next power of two using bit manipulation?

You can use bit shifting techniques, filling all bits below the highest set bit, to find the next power of two.

What is the time complexity of solving this problem?

The time complexity depends on the method used for bit manipulation, but typically it is O(log n).

What should I do if n is already a number with all set bits?

If n already has all set bits, the answer is simply n itself.

How does GhostInterview help with this problem?

GhostInterview guides you through the bit manipulation approach and ensures you avoid unnecessary calculations, offering efficient solutions.

terminal

Solution

Solution 1: Bit Manipulation

We start with $x = 1$ and continuously left shift $x$ until $x - 1 \geq n$. At this point, $x - 1$ is the answer we are looking for.

1

2

3

4

5

6

class Solution:
    def smallestNumber(self, n: int) -> int:
        x = 1
        while x - 1 < n:
            x <<= 1
        return x - 1

Continue Practicing

#3307 find the k th character in string game ii #3304 find the k th character in string game i #3444 minimum increments for target multiples in an array