We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Smallest Number With All Set Bits

Difficulty: Easy

Problem Description

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.

Key Insights

  • A number with all set bits in binary is of the form (2^m - 1) for some integer m.
  • The smallest number with all set bits greater than or equal to n can be found by determining the next power of two that covers n.
  • This can be efficiently calculated using bit manipulation.

Space and Time Complexity

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

Solution

To solve the problem, we can use the following approach:

  1. Identify the smallest power of two greater than or equal to n.
  2. Generate the number with all set bits corresponding to that power of two.
  3. This is done by taking the power of two and subtracting one from it.

For example, for n = 5, the next power of two is 8 (2^3), and the smallest number with all set bits is 7 (which is 2^3 - 1).

Code Solutions

def smallest_with_all_set_bits(n):
    # Initialize a variable to find the next power of 2
    power = 1
    # Find the smallest power of 2 that is greater than or equal to n
    while power < n:
        power <<= 1  # Equivalent to power = power * 2
    # Return the number with all set bits corresponding to the found power
    return power - 1

# Example usage
print(smallest_with_all_set_bits(5))  # Output: 7
print(smallest_with_all_set_bits(10)) # Output: 15
← Back to All Questions