Smallest Number With All Set Bits — Easy Problem & Solution

Problem statement

Return the smallest number x that is at least n and whose binary representation is all ones — that is, x is 1, 3, 7, 15, 31, and so on.

Example 1

Input: n = 5
Output: 7
Explanation: 7 is 111 in binary and is the smallest all-ones value at or above 5.

Example 2

Input: n = 10
Output: 15

Example 3

Input: n = 3
Output: 3
Explanation: 3 is already all ones.

Constraints

• 1 <= n <= 1000

How to solve Smallest Number With All Set Bits

All-ones numbers form the sequence 1, 3, 7, 15, …, each obtained from the previous by appending a one bit. Walk the sequence until it reaches n.

Approach

1. Start v at 1.
2. While v < n, replace v with 2v + 1.
3. Return v.

Why it works

2v + 1 shifts the binary form left and sets the new low bit, so the sequence enumerates 2^k - 1 in increasing order. The first term at or above n is therefore the smallest such value.

Complexity

• Time — O(log n)
• Space — O(1)

Pitfalls

• Starting at 0 never escapes — 2 * 0 + 1 = 1 works, but v = 0 with v *= 2 would not.
• Rounding n up to a power of two gives 8 for n = 5, which is not all ones.

Reference solution

Python

def smallestNumber(n: int) -> int:
    v = 1
    while v < n:
        v = v * 2 + 1
    return v

JavaScript

var smallestNumber = function(n) {
    var v = 1;
    while (v < n) v = v * 2 + 1;
    return v;
};

Also on the editorial tab: C, C#, C++, Go, Java, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

More math problems

• Number of Bit Changes to Make Two Integers Equal Easy
• Find the XOR of Numbers Which Appear Twice Easy
• Binary Watch Easy
• Shortest Subarray With OR at Least K I Easy
• Maximum Strong Pair XOR I Easy
• Complement of Base 10 Integer Easy