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

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Smallest Number With All Set Bits

Number: 3676

Difficulty: Easy

Paid? No

Companies: N/A

Problem Description

Given a positive number n, find the smallest number x greater than or equal to n such that the binary representation of x contains only set bits (i.e., all 1's). Numbers with only set bits are of the form (2^k - 1). For example, if n = 5, then x = 7 because 7 in binary is "111".

Key Insights

  • Numbers with only set bits are of the form (2^k - 1) for some integer k.
  • To solve the problem, find the smallest k such that (2^k - 1) is greater than or equal to n.
  • This problem takes advantage of bit manipulation and properties of numbers represented in binary.

Space and Time Complexity

Time Complexity: O(log n) – The loop iterates roughly the number of bits required to represent n. Space Complexity: O(1) – Only a few variables are used.

Solution

We iterate over increasing values of k and compute candidate = (2^k - 1). When candidate is greater than or equal to n, we return candidate. We use arithmetic operations without any additional data structure.

Code Solutions

# Function to compute the smallest number with all set bits
def smallest_all_set_bits(n):
    k = 1  # start with one set bit
    while (2 ** k - 1) < n:  # check if current candidate is less than n
        k += 1  # increase k to include more set bits
    return 2 ** k - 1  # return the smallest number with k set bits

# Example usage:
n = 10
result = smallest_all_set_bits(n)
print(result)  # Expected output: 15
← Back to All Questions