Smallest Number With All Set Bits

main.md

Question

Approach

I realized that a number whose binary representation contains only set bits is of the form ( 2^k - 1 ) (like 1, 3, 7, 15, 31, …). So I can find the smallest such number that is greater than or equal to n. I start from 1 and keep generating numbers of this form until I find one ≥ n, then return it.

Implementation

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

Complexities

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