3370. Smallest Number With All Set Bits

Time: O(1)

Space: O(1)

Approach

Return 2^(floor(log2(n))+1) - 1 = all bits set up to bit count of n.

Key Techniques

Math problems test number theory, combinatorics, and modular arithmetic. Common tools: GCD/LCM (Euclidean algorithm), prime sieve, modular inverse (Fermat's little theorem), digit manipulation, and bit tricks. Overflow is a key concern in C# — use long when products may exceed 2³¹.

Bit Manipulation

Bit manipulation uses bitwise operators (&, |, ^, ~, <<, >>) for compact and fast solutions. Key tricks: x & (x-1) clears lowest set bit, x ^ x = 0 (XOR cancellation), and bitmask DP represents subsets as integers. In C#, use int (32-bit) or long (64-bit) for bitmasking.

3370.cs

// Approach: Return 2^(floor(log2(n))+1) - 1 = all bits set up to bit count of n.
// Time: O(1) Space: O(1)

public class Solution
{
    public int SmallestNumber(int n)
    {
        // Initialize power of 2 starting from 2^0 = 1
        int powerOfTwo = 1;

        // Keep doubling the power of 2 until (powerOfTwo - 1) is at least n
        // This finds the smallest k such that 2^k - 1 >= n
        while (powerOfTwo - 1 < n)
            // Left shift by 1 is equivalent to multiplying by 2
            // powerOfTwo becomes 2, 4, 8, 16, 32, ...
            powerOfTwo <<= 1;

        // Return 2^k - 1, which is a number with all k bits set to 1
        // Examples: 1 (2^1-1), 3 (2^2-1), 7 (2^3-1), 15 (2^4-1), ...
        return powerOfTwo - 1;
    }
}

Was this solution helpful?