Problem Statement in English

Given an integer n, return the smallest integer that has all bits set to 1 in its binary representation and is greater than or equal to n.

Approach

We essentially need to find the smallest number which is of the form 2^k - 1 (which has all bits set to 1 in binary) that is greater than or equal to n.

So we need to find the next greatest power of 2 that is greater than n, and then subtract 1 from it.

Solution in Python


class Solution:
    def smallestNumber(self, n: int) -> int:
        return 2 ** (floor(log2(n)) + 1) - 1

Complexity

  • Time: $O(1)$
    Since we essentially perform a single calculation.

  • Space: $O(1)$
    Since we only use a constant amount of space.

And we are done.