Jobs

Interviews

Discussions

Number of 1 Bits

Easy

Number of 1 Bits

Easy

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 range of possible values for the unsigned integer n?
Is the input guaranteed to be a valid unsigned integer, or should I handle potential invalid input?
Should I aim for a specific time complexity (e.g., O(1) assuming a fixed integer size), or is minimizing space more important?
Are there any specific constraints on the programming language features I can use?
Can you provide a few example inputs and their corresponding outputs to ensure I understand the problem correctly?

Brute Force Solution

Approach

We want to figure out how many '1's are in a given number when we write it in binary (using only 1s and 0s). The brute force method is simple: we examine each digit of the binary representation one by one.

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

Look at the rightmost digit of the binary number.
If that digit is a '1', add one to our running count.
Shift all the digits one position to the right so we can examine the next digit, and repeat this process.
Continue shifting and checking until there are no digits left to examine.
The final count is the total number of '1's in the binary representation of the number.

Code Implementation

def count_number_of_one_bits_brute_force(number):
    number_of_one_bits = 0

    # Iterate until the number becomes zero
    while number:

        # Check the rightmost bit if it is one
        if number & 1:
            number_of_one_bits += 1

        # Right-shift the number by 1. This moves to the next bit.
        number = number >> 1

    return number_of_one_bits

Big(O) Analysis

Time Complexity

O(1) – The algorithm iterates a number of times proportional to the number of bits in the input number 'n'. Since the number of bits in an integer is fixed (typically 32 or 64 bits), the number of iterations is constant regardless of the magnitude of the input number. Therefore, the time complexity is O(1) because it performs a fixed number of operations.

Space Complexity

O(1) – The algorithm uses a single variable to store the count of 1 bits, and it shifts the input number in place (or uses a constant number of registers to represent the number during the shifting process). No auxiliary data structures like arrays or hash maps are created. Therefore, the space required remains constant irrespective of the input number's size (N, where N is the number of bits in the input). Consequently, the auxiliary space complexity is O(1).

Optimal Solution

Approach

The most efficient way to count the number of ones in a binary number takes advantage of a bitwise trick. This trick cleverly isolates and removes the rightmost one bit in each step until the number becomes zero, and each removal represents a 'one' we've counted.

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

Look at the number you've been given.
Subtract one from the number.
Perform a bitwise 'AND' operation between the original number and the result of the subtraction.
This 'AND' operation will effectively turn the rightmost '1' into a '0'.
Increment a counter to keep track of how many '1' bits we've found.
Repeat steps 2-5 until the number becomes zero.
The counter now holds the total number of '1' bits that were originally in the number.

Code Implementation

def count_number_of_set_bits(number):
    set_bit_count = 0

    # Iterate until the number becomes zero
    while number:

        # This operation isolates the rightmost 1-bit
        number &= (number - 1)

        set_bit_count += 1

    return set_bit_count

Big(O) Analysis

Time Complexity

O(log n) – The algorithm's runtime is determined by the number of '1' bits in the input number, not the magnitude of the number 'n' itself. The while loop iterates once for each '1' bit. In the worst-case scenario, all bits are '1', and the loop runs log n times where n is the number. However, since we are performing a constant amount of work in each iteration (bitwise AND, subtraction, and incrementing a counter), the overall time complexity depends on the number of 1's. More correctly, the time complexity is O(k) where k is the number of 1 bits. In the worst-case scenario, where k equals log n, the runtime is O(log n).

Space Complexity

O(1) – The algorithm utilizes only a single integer variable, the counter, to keep track of the number of 1 bits found. The original number is directly modified through bitwise operations and subtraction, and no additional data structures are used to store intermediate results. Therefore, the auxiliary space used is constant and independent of the input number. Consequently, the space complexity is O(1).

Edge Cases

Case	How to Handle
Input is 0	The algorithm should correctly return 0, as the binary representation has no 1s.
Input is the maximum unsigned integer	The algorithm should correctly return the number of bits in the integer type (e.g., 32 for a 32-bit integer).
Input is a power of 2 (e.g., 1, 2, 4, 8)	The algorithm should return 1, as only one bit is set.
Input has alternating 0s and 1s	The bitwise operations will correctly count the 1s regardless of their pattern.
Language-specific integer overflow	Since the input is an unsigned integer, overflow isn't a primary concern within the given context of bit counting; the algorithm will operate on the bits present within the data type's capacity.
Negative Input	Since the input is an unsigned integer, negative numbers are not a valid input; the function should assume valid input within the unsigned integer range.
Very large sparse inputs (mostly 0s with a few scattered 1s)	Algorithms like the bit manipulation trick `n &= (n - 1)` are designed to efficiently handle this case by iterating only as many times as there are 1s.
Integer that is one less than a power of 2 (e.g., 3, 7, 15)	The algorithm should correctly calculate the number of 1s; all bits up to the leading bit will be set to 1.

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 range of possible values for the unsigned integer n?
Is the input guaranteed to be a valid unsigned integer, or should I handle potential invalid input?
Should I aim for a specific time complexity (e.g., O(1) assuming a fixed integer size), or is minimizing space more important?
Are there any specific constraints on the programming language features I can use?
Can you provide a few example inputs and their corresponding outputs to ensure I understand the problem correctly?

Brute Force Solution

Approach

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

Look at the rightmost digit of the binary number.
If that digit is a '1', add one to our running count.
Shift all the digits one position to the right so we can examine the next digit, and repeat this process.
Continue shifting and checking until there are no digits left to examine.
The final count is the total number of '1's in the binary representation of the number.

Code Implementation

def count_number_of_one_bits_brute_force(number):
    number_of_one_bits = 0

    # Iterate until the number becomes zero
    while number:

        # Check the rightmost bit if it is one
        if number & 1:
            number_of_one_bits += 1

        # Right-shift the number by 1. This moves to the next bit.
        number = number >> 1

    return number_of_one_bits

Big(O) Analysis

Time Complexity

Space Complexity

Optimal Solution

Approach

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

Look at the number you've been given.
Subtract one from the number.
Perform a bitwise 'AND' operation between the original number and the result of the subtraction.
This 'AND' operation will effectively turn the rightmost '1' into a '0'.
Increment a counter to keep track of how many '1' bits we've found.
Repeat steps 2-5 until the number becomes zero.
The counter now holds the total number of '1' bits that were originally in the number.

Code Implementation

def count_number_of_set_bits(number):
    set_bit_count = 0

    # Iterate until the number becomes zero
    while number:

        # This operation isolates the rightmost 1-bit
        number &= (number - 1)

        set_bit_count += 1

    return set_bit_count

Big(O) Analysis

Time Complexity

Space Complexity

Edge Cases

Case	How to Handle
Input is 0	The algorithm should correctly return 0, as the binary representation has no 1s.
Input is the maximum unsigned integer	The algorithm should correctly return the number of bits in the integer type (e.g., 32 for a 32-bit integer).
Input is a power of 2 (e.g., 1, 2, 4, 8)	The algorithm should return 1, as only one bit is set.
Input has alternating 0s and 1s	The bitwise operations will correctly count the 1s regardless of their pattern.
Language-specific integer overflow	Since the input is an unsigned integer, overflow isn't a primary concern within the given context of bit counting; the algorithm will operate on the bits present within the data type's capacity.
Negative Input	Since the input is an unsigned integer, negative numbers are not a valid input; the function should assume valid input within the unsigned integer range.
Very large sparse inputs (mostly 0s with a few scattered 1s)	Algorithms like the bit manipulation trick `n &= (n - 1)` are designed to efficiently handle this case by iterating only as many times as there are 1s.
Integer that is one less than a power of 2 (e.g., 3, 7, 15)	The algorithm should correctly calculate the number of 1s; all bits up to the leading bit will be set to 1.