Smallest Number With All Set Bits

EASY

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

Example 1:

Input: n = 5

Output: 7

Explanation:

The binary representation of 7 is "111".

Example 2:

Input: n = 10

Output: 15

Explanation:

The binary representation of 15 is "1111".

Example 3:

Input: n = 3

Output: 3

Explanation:

The binary representation of 3 is "11".

Constraints:

1 <= n <= 1000

Approaches

Checkout 3 different approaches to solve Smallest Number With All Set Bits. Click on different approaches to view the approach and algorithm in detail.

Brute Force Iteration

This approach involves checking every number starting from n until we find one whose binary representation consists solely of set bits (1s).

Algorithm

Start a loop with a variable x initialized to n.
In each iteration, check if x is a number with all bits set. A number y has all its bits set if it is of the form 2^k - 1. A clever bitwise trick to check this condition is (y & (y + 1)) == 0.
If the condition is met, we have found our smallest number x >= n and we return it.
If the condition is not met, we increment x by 1 and continue the loop.

We start a loop with a variable x initialized to n. In each iteration, we check if x is a number with all bits set. A number y has all its bits set if it is of the form 2^k - 1. A clever bitwise trick to check this condition is (y & (y + 1)) == 0. This works because adding 1 to a number composed of all 1s (like ...0111) results in a number that is a power of two (...1000), and the bitwise AND of these two numbers will be zero. If the condition is met, we have found our smallest number x >= n and we return it. If the condition is not met, we increment x by 1 and continue the loop. The loop is guaranteed to terminate because the sequence of numbers with all set bits is infinite (1, 3, 7, 15, ...), so we will eventually find one.

class Solution {
    public int smallestNumberWithAllSetBits(int n) {
        int x = n;
        while (true) {
            // A number has all set bits if (x & (x + 1)) == 0
            // Example: x = 7 (0111), x + 1 = 8 (1000). 7 & 8 = 0.
            // This check is valid for x > 0.
            if ((x & (x + 1)) == 0) {
                return x;
            }
            x++;
        }
    }
}

Complexity Analysis

Time Complexity: O(M - n), where `M` is the smallest number with all set bits that is greater than or equal to `n`. In the worst case, `n` could be `2^k`, and `M` would be `2^(k+1) - 1`. The number of iterations would be `2^k - 1`, which is roughly `n`. So, the complexity is approximately O(n).Space Complexity: O(1), as we only use a constant amount of extra space.

Pros and Cons

Pros:

Simple to understand and implement.

Cons:

Inefficient for large n, especially when n is just slightly larger than a number with all set bits (e.g., n = 2^k). The number of iterations can be proportional to n.

Code Solutions

Checking out 3 solutions in different languages for Smallest Number With All Set Bits. Click on different languages to view the code.

class Solution {
public
  int smallestNumber(int n) {
    int x = 1;
    while (x - 1 < n) {
      x <<= 1;
    }
    return x - 1;
  }
}

Video Solution

Watch the video walkthrough for Smallest Number With All Set Bits

Patterns:

MathBit Manipulation

Smallest Number With All Set Bits

Description

Approaches

Brute Force Iteration

Algorithm

Complexity Analysis

Pros and Cons

Code Solutions

Video Solution

Similar Questions

Patterns:

On this page

Subscribe to Scale Engineer newsletter