Smallest Number With All Set Bits - Practice Coding Problems

Smallest Number With All Set Bits - Problem

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 (all bits are 1).

A number with all set bits means every bit position in its binary representation is 1. For example:

1 (binary: 1) - all bits are 1
3 (binary: 11) - all bits are 1
7 (binary: 111) - all bits are 1
15 (binary: 1111) - all bits are 1

Input & Output

Example 1 — Basic Case

$ Input: n = 5

› Output: 7

💡 Note: 5 in binary is 101. The smallest number ≥ 5 with all set bits is 7 (111 in binary).

Example 2 — Already All Set Bits

$ Input: n = 3

› Output: 3

💡 Note: 3 in binary is 11. Since all bits are already set, return 3.

Example 3 — Single Bit

$ Input: n = 1

› Output: 1

💡 Note: 1 in binary is 1. Since the only bit is set, return 1.

Constraints

1 ≤ n ≤ 10⁹

Visualization

Tap to expand

Understanding the Visualization

Input

Given positive integer n

Process

Find smallest x ≥ n where all bits are 1

Output

Return the number with all set bits

Key Takeaway

🎯 Key Insight: All numbers with set bits follow 2^k - 1 pattern, so calculate directly instead of checking each number

Asked in

G Google 25 M Microsoft 18 A Amazon 15

The key insight is that numbers with all set bits follow the pattern 2^k - 1. We can find the bit length of n and calculate the next such number directly. Best approach uses bit manipulation with Time: O(1), Space: O(1).

Common Approaches

Approach	Time	Space	Notes
✓ Single Pass Optimal	O(1)	O(1)	Use bit shifting to find the next power of 2 minus 1 in O(1) time
Brute Force Check	O(k × log k)	O(1)	Check each number starting from n until we find one with all bits set
Bit Length Calculation	O(log n)	O(1)	Find bit length of n, then calculate 2^length - 1

Single Pass Optimal — Algorithm Steps

Find highest set bit position in n
Create mask with all bits set from 0 to that position
If result < n, shift mask left by 1 and subtract 1

Visualization

Tap to expand

Step-by-Step Walkthrough

Find MSB

Locate most significant bit

Calculate Power

Use 2^(pos+1) - 1 formula

Return Result

Get answer in O(1) time

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#include <stdbool.h>

int solution(int n) {
    // Special case: if n is already 2^k - 1
    if ((n & (n + 1)) == 0) {
        return n;
    }
    
    // Find the position of the most significant bit
    int msbPos = floor(log2(n));
    
    // Create the next number with all bits set
    // This is 2^(msb_pos + 1) - 1
    int result = (1 << (msbPos + 1)) - 1;
    
    return result;
}

int main() {
    int n;
    scanf("%d", &n);
    int result = solution(n);
    printf("%d\n", result);
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(1)

Uses only constant time bit operations

✓ Linear Growth

Space Complexity

O(1)

Only using constant extra variables

✓ Linear Space

12.5K Views

Medium Frequency

~15 min Avg. Time

485 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Single Pass Optimal — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler