Jobs

Interviews

Discussions

Smallest Number With All Set Bits

#1602 Most AskedEasy

Smallest Number With All Set Bits #1602 Most Asked

Easy

Google

5 views

Topics:

Bit Manipulation

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

Try coding it in LeetCode

Smallest Number With All Set Bits

#1602 Most AskedEasy

Smallest Number With All Set Bits #1602 Most Asked

Easy

Google

5 views

Topics:

Bit Manipulation

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

Try coding it in LeetCode

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What is the maximum number of bits that can be set? Is there an upper bound on the number we should consider?
Will the input always be a valid positive integer, or should I handle cases where it is zero or negative?
If there are multiple numbers with the same smallest number of set bits, should I return the smallest of those numbers?
Can you clarify what you mean by 'set bits'? Are you referring to the bits with a value of 1 in the binary representation of a number?
Is there a limit to the size of the integer the function should handle (e.g., 32-bit or 64-bit)? Should I expect overflow issues?

Brute Force Solution

Approach

The brute force method for this problem involves systematically checking each number, starting from one, until we find the one that satisfies our condition. We're essentially going through all the numbers one by one, testing each to see if its binary representation has all bits set up to a certain point.

Here's how the algorithm would work step-by-step:

Begin with the number one.
Check if all the bits are set in its binary representation, up to the highest bit that's 'on'.
If they are, we've found our answer; stop.
If not, increment the number by one.
Repeat the checking process for this new number.
Continue this process, incrementing and checking, until we discover a number where all bits are set from the least significant bit up to the most significant bit that is set.

Code Implementation

def find_smallest_number_with_all_set_bits():
    number = 1

    while True:
        binary_representation = bin(number)[2:]

        # Determine the highest bit that is set
        highest_set_bit_index = len(binary_representation) - 1

        all_bits_set = True

        # Check if all bits are set up to the highest set bit.
        for bit_index in range(highest_set_bit_index + 1):
            if binary_representation[highest_set_bit_index - bit_index] == '0':
                all_bits_set = False
                break

        if all_bits_set:
            # Found a number with all set bits
            return number

        number += 1

Big(O) Analysis

Time Complexity

O(2^n) – The brute force approach iterates through numbers starting from 1. In the worst case, it has to check numbers up to the smallest number where all bits are set up to the nth bit. This number is essentially 2^n - 1. For each number checked, determining if all bits are set up to the highest set bit requires examining up to n bits. Therefore, the outer loop goes up to 2^n and the inner loop takes O(n) to verify the set bits, giving a complexity approaching O(n * 2^n). However, since 2^n dominates n, we can simplify to O(2^n).

Space Complexity

O(1) – The brute force method iteratively checks each number, incrementing from 1 until a number with all bits set is found. The algorithm only uses a constant amount of extra space to store the current number being checked and potentially a flag indicating if all bits are set. The space used does not depend on the size of any input N, making the auxiliary space complexity constant.

Optimal Solution

Approach

The goal is to find the smallest whole number that contains all the '1' bits from a given number. The trick is to realize we're really just looking for the next power of two that's larger than the input number. This lets us directly calculate the answer without trying a bunch of different numbers.

Here's how the algorithm would work step-by-step:

Take the input number.
Figure out the next power of two larger than that number.
That power of two is your answer.

Code Implementation

def smallest_number_with_all_set_bits(given_number):
    next_power_of_two = 1

    # Find the next power of 2 greater than the given number
    while next_power_of_two <= given_number:
        next_power_of_two <<= 1

    # We must subtract one to set all bits less significant than the MSB
    return next_power_of_two

Big(O) Analysis

Time Complexity

O(1) – The algorithm determines the next power of two greater than the input number. This operation involves a fixed number of bitwise operations regardless of the input value. Since the number of operations is constant and does not depend on the size of the input (n), the time complexity is O(1).

Space Complexity

O(1) – The described algorithm calculates the next power of two without using any auxiliary data structures like arrays, lists, or hash maps. It operates directly on the input number and stores intermediate results (like the power of two being checked) in a fixed number of variables. The amount of memory used does not depend on the input number (N), making the space complexity constant. Thus, the space complexity is O(1).

Edge Cases

Case	How to Handle
Input is zero	Return 0 because zero has no set bits.
Input is negative	Return 1 as it is smallest number with all set bits using two's complement representation depending on the specification.
Input is very large integer	May need to return Long.MAX_VALUE or a sentinel value signifying an error depending on the specification.
Integer Overflow	Ensure the return type is large enough to represent the result, potentially using long or BigInteger in languages like Java and Python.
Minimum Integer Value (Integer.MIN_VALUE)	Handle the minimum integer value appropriately based on two's complement representation by setting all bits to 1 using appropriate mask.
Input is a power of 2	Return the next higher power of 2 minus 1.
The input has all bits set	Return the input as it is already the smallest number with all bits set.
No valid solution exists (e.g. if a specified maximum bit length is too short)	Return -1 or throw an exception indicating that no valid solution can be found.

Input is zero

How to Handle:

Return 0 because zero has no set bits.

Input is negative

How to Handle:

Return 1 as it is smallest number with all set bits using two's complement representation depending on the specification.

Input is very large integer

How to Handle:

May need to return Long.MAX_VALUE or a sentinel value signifying an error depending on the specification.

Integer Overflow

How to Handle:

Ensure the return type is large enough to represent the result, potentially using long or BigInteger in languages like Java and Python.

Minimum Integer Value (Integer.MIN_VALUE)

How to Handle:

Handle the minimum integer value appropriately based on two's complement representation by setting all bits to 1 using appropriate mask.

Input is a power of 2

How to Handle:

Return the next higher power of 2 minus 1.

The input has all bits set

How to Handle:

Return the input as it is already the smallest number with all bits set.

No valid solution exists (e.g. if a specified maximum bit length is too short)

How to Handle:

Return -1 or throw an exception indicating that no valid solution can be found.

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What is the maximum number of bits that can be set? Is there an upper bound on the number we should consider?
Will the input always be a valid positive integer, or should I handle cases where it is zero or negative?
If there are multiple numbers with the same smallest number of set bits, should I return the smallest of those numbers?
Can you clarify what you mean by 'set bits'? Are you referring to the bits with a value of 1 in the binary representation of a number?
Is there a limit to the size of the integer the function should handle (e.g., 32-bit or 64-bit)? Should I expect overflow issues?

Brute Force Solution

Approach

Here's how the algorithm would work step-by-step:

Begin with the number one.
Check if all the bits are set in its binary representation, up to the highest bit that's 'on'.
If they are, we've found our answer; stop.
If not, increment the number by one.
Repeat the checking process for this new number.
Continue this process, incrementing and checking, until we discover a number where all bits are set from the least significant bit up to the most significant bit that is set.

Code Implementation

def find_smallest_number_with_all_set_bits():
    number = 1

    while True:
        binary_representation = bin(number)[2:]

        # Determine the highest bit that is set
        highest_set_bit_index = len(binary_representation) - 1

        all_bits_set = True

        # Check if all bits are set up to the highest set bit.
        for bit_index in range(highest_set_bit_index + 1):
            if binary_representation[highest_set_bit_index - bit_index] == '0':
                all_bits_set = False
                break

        if all_bits_set:
            # Found a number with all set bits
            return number

        number += 1

Big(O) Analysis

Time Complexity

Space Complexity

Optimal Solution

Approach

Here's how the algorithm would work step-by-step:

Take the input number.
Figure out the next power of two larger than that number.
That power of two is your answer.

Code Implementation

def smallest_number_with_all_set_bits(given_number):
    next_power_of_two = 1

    # Find the next power of 2 greater than the given number
    while next_power_of_two <= given_number:
        next_power_of_two <<= 1

    # We must subtract one to set all bits less significant than the MSB
    return next_power_of_two

Big(O) Analysis

Time Complexity

Space Complexity

Edge Cases

Case	How to Handle
Input is zero	Return 0 because zero has no set bits.
Input is negative	Return 1 as it is smallest number with all set bits using two's complement representation depending on the specification.
Input is very large integer	May need to return Long.MAX_VALUE or a sentinel value signifying an error depending on the specification.
Integer Overflow	Ensure the return type is large enough to represent the result, potentially using long or BigInteger in languages like Java and Python.
Minimum Integer Value (Integer.MIN_VALUE)	Handle the minimum integer value appropriately based on two's complement representation by setting all bits to 1 using appropriate mask.
Input is a power of 2	Return the next higher power of 2 minus 1.
The input has all bits set	Return the input as it is already the smallest number with all bits set.
No valid solution exists (e.g. if a specified maximum bit length is too short)	Return -1 or throw an exception indicating that no valid solution can be found.

Input is zero

How to Handle:

Return 0 because zero has no set bits.

Input is negative

How to Handle:

Return 1 as it is smallest number with all set bits using two's complement representation depending on the specification.

Input is very large integer

How to Handle:

May need to return Long.MAX_VALUE or a sentinel value signifying an error depending on the specification.

Integer Overflow

How to Handle:

Ensure the return type is large enough to represent the result, potentially using long or BigInteger in languages like Java and Python.

Minimum Integer Value (Integer.MIN_VALUE)

How to Handle:

Handle the minimum integer value appropriately based on two's complement representation by setting all bits to 1 using appropriate mask.

Input is a power of 2

How to Handle:

Return the next higher power of 2 minus 1.

The input has all bits set

How to Handle:

Return the input as it is already the smallest number with all bits set.

No valid solution exists (e.g. if a specified maximum bit length is too short)

How to Handle:

Return -1 or throw an exception indicating that no valid solution can be found.

0/1916 Google questions completed

0/1916 completed