What is the time complexity of the Bit Manipulation approach?

The time complexity is O(1) as it involves a single left shift operation and subtraction.

What is the time complexity of the Math Formula approach?

The time complexity is O(1) as it involves computing a power and subtraction.

Which approach is more efficient?

The Bit Manipulation approach is more efficient as it uses bitwise operations directly without calling math library functions.

Smallest Number With All Set Bits

Difficulty: Easy | Acceptance: 80.30% | Paid: No Topics: Math, Bit Manipulation

You are given a positive integer n. Return the smallest number x such that x has all its bits set and has exactly n bits.

A number has all its bits set if every bit in its binary representation is 1. For example, 7 (binary 111) has all its bits set, while 5 (binary 101) does not.

Examples
Constraints
Bit Manipulation Approach
Math Formula Approach

Examples

Input: n = 3
Output: 7
Explanation: 7 in binary is 111, which has all 3 bits set.

Input: n = 1
Output: 1
Explanation: 1 in binary is 1, which has all 1 bit set.

Input: n = 4
Output: 15
Explanation: 15 in binary is 1111, which has all 4 bits set.

Constraints

1 <= n <= 20

Bit Manipulation

Intuition A number with all n bits set is simply 2ⁿ - 1, which can be efficiently computed using the left shift operator.

Steps

Left shift 1 by n positions to get 2ⁿ
Subtract 1 to get the number with all n bits set

python

class Solution:
    def smallestNumber(self, n: int) -&gt; int:
        return (1 &lt;&lt; n) - 1

Complexity

Time: O(1)
Space: O(1)
Notes: Most efficient approach using bitwise operations

Math Formula

Intuition The smallest number with all n bits set follows the mathematical formula 2ⁿ - 1.

Steps

Calculate 2 raised to the power of n
Subtract 1 from the result

python

class Solution:
    def smallestNumber(self, n: int) -&gt; int:
        return 2 ** n - 1

Complexity

Time: O(1)
Space: O(1)
Notes: Uses math library functions, slightly less efficient than bit manipulation