3370. Smallest Number With All Set Bits

#php #leetcode #algorithms #programming

Difficulty: Easy

Topics: Math, Bit Manipulation, Weekly Contest 426

You are given a positive number n.

Return the smallest number x greater than or equal to n, such that the binary representation of x contains only set bits¹

Example 1:

Input: n = 5
Output: 7
Explanation: The binary representation of 7 is "111".

Example 2:

Input: n = 10
Output: 15
Explanation: The binary representation of 15 is "1111".

Example 3:

Input: n = 3
Output: 3
Explanation: The binary representation of 3 is "11".

Constraints:

1 <= n <= 1000

Hint:

Find the strictly greater power of 2, and subtract 1 from it.

Solution:

We need to find the smallest number ≥ n that has all 1s in its binary representation.

The key insight is that numbers with all set bits are of the form 2^k - 1 (like 1, 3, 7, 15, 31, etc.). So I need to find the smallest number of this form that is ≥ n.

Here's my approach:

Find the number of bits needed to represent n
The candidate numbers are (1 << k) - 1 where k is the bit length
If n itself is already all 1s, return n
Otherwise, return the next number with all 1s

Let's implement this solution in PHP: 3370. Smallest Number With All Set Bits

<?php
/**
 * @param Integer $n
 * @return Integer
 */
function smallestNumber($n) {
    ...
    ...
    ...
    /**
     * go to ./solution.php
     */
}

// Test cases
echo smallestNumber(5) . PHP_EOL;  // Output: 7
echo smallestNumber(10) . PHP_EOL; // Output: 15
echo smallestNumber(3) . PHP_EOL;  // Output: 3
?>

Explanation:

Check if n is already all 1s: (n & (n + 1)) == 0 is a bit trick to check if a number is of the form 2^k - 1. For example:
- n=3 (binary 11): 3 & 4 = 0 ✓
- n=7 (binary 111): 7 & 8 = 0 ✓
Find bit length: We count how many bits are needed to represent n by repeatedly shifting right until the number becomes 0.
Calculate result: (1 << bitLength) - 1 gives us the next number with all bits set. For example:
- If n=5, bitLength=3, result = (1 << 3) - 1 = 8 - 1 = 7
- If n=10, bitLength=4, result = (1 << 4) - 1 = 16 - 1 = 15

Let's test with the examples:

n=5: bitLength=3, result=7 ✓
n=10: bitLength=4, result=15 ✓
n=3: Already all 1s, returns 3 ✓

The time complexity is O(log n) and space complexity is O(1).

Contact Links

If you found this series helpful, please consider giving the repository a star on GitHub or sharing the post on your favorite social networks 😍. Your support would mean a lot to me!