Editorial

Solution walkthrough

Review the explanation, then compare the reference implementation.

Video explanation

Solution

Intuition

Positive numbers whose binary representation contains only ones are 1, 3, 7, 15, and so on. Each is obtained from the previous one by shifting left once and appending a one, which is the same as multiplying by two and adding one.

Approach

Start with x = 1. While x is smaller than n, replace it with 2 * x + 1. Return the first value that is at least n.

Every generated value has all bits set, and the sequence lists all such positive values in increasing order. Therefore stopping at the first qualifying value gives the smallest answer. If n already has only set bits, the loop reaches it exactly and does not advance to the next value.

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

        while x < n:
            x = x * 2 + 1

        return x

Complexity analysis

Time: O(log n). Auxiliary space: O(1).