Jobs

Interviews

Discussions

Counting Bits

Easy

Amazon

3 views

Topics:

ArraysDynamic ProgrammingBit Manipulation

Given an integer n, return an array ans of length n + 1 such that for each i (0 <= i <= n), ans[i] is the number of 1's in the binary representation of i.

Example 1:

Input: n = 2
Output: [0,1,1]
Explanation:
0 --> 0
1 --> 1
2 --> 10

Example 2:

Input: n = 5
Output: [0,1,1,2,1,2]
Explanation:
0 --> 0
1 --> 1
2 --> 10
3 --> 11
4 --> 100
5 --> 101

Constraints:

0 <= n <= 10⁵

Follow up:

It is very easy to come up with a solution with a runtime of O(n log n). Can you do it in linear time O(n) and possibly in a single pass?
Can you do it without using any built-in function (i.e., like __builtin_popcount in C++)?

Counting Bits

Easy

Amazon

3 views

Topics:

ArraysDynamic ProgrammingBit Manipulation

Given an integer n, return an array ans of length n + 1 such that for each i (0 <= i <= n), ans[i] is the number of 1's in the binary representation of i.

Example 1:

Input: n = 2
Output: [0,1,1]
Explanation:
0 --> 0
1 --> 1
2 --> 10

Example 2:

Input: n = 5
Output: [0,1,1,2,1,2]
Explanation:
0 --> 0
1 --> 1
2 --> 10
3 --> 11
4 --> 100
5 --> 101

Constraints:

0 <= n <= 10⁵

Follow up:

It is very easy to come up with a solution with a runtime of O(n log n). Can you do it in linear time O(n) and possibly in a single pass?
Can you do it without using any built-in function (i.e., like __builtin_popcount in C++)?

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 non-negative integer limit for `n`? Specifically, what is the maximum possible value of `n`?
Should I return an array of length `n + 1` where `result[i]` represents the number of set bits in the binary representation of `i`?
Are there any specific memory constraints I should be aware of?
Is `n` guaranteed to be a non-negative integer, or should I handle invalid input types (e.g., null, negative numbers, strings)?
For the purpose of this problem, is the definition of 'set bits' universally understood to mean the count of bits that are 1 in the binary representation of an integer?

Brute Force Solution

Approach

The brute force approach directly computes the number of '1' bits for every number in the given range. We will examine each number individually, one after another. We count the number of set bits in each number and save that count.

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

Start with the first number in the range (which is zero).
Figure out how many '1's are in the binary representation of that number.
Record this count of '1's.
Move to the next number.
Again, figure out how many '1's are in the binary representation of that number.
Record this count of '1's.
Repeat this process for every number in the range, counting the '1's in each one and saving the result.
When you're done with all the numbers, you'll have a list of counts representing the number of '1's in each number from zero to the end of the range.

Code Implementation

def counting_bits_brute_force(number_range):    results = []
    # Iterate through each number in the range. 
    for number in range(number_range + 1):
        binary_representation = bin(number)[2:]
        bit_count = 0
        # Count the number of '1' bits. Necessary for the problem statement.
        for bit in binary_representation:
            if bit == '1':
                bit_count += 1

        results.append(bit_count)
    return results

Big(O) Analysis

Time Complexity

O(n log n) – The algorithm iterates through each number from 0 to n (exclusive), resulting in n iterations. For each number, the algorithm counts the number of set bits. Counting set bits for a number i takes O(log i) time in the worst case, as the number of bits to examine grows logarithmically with the value of i. Therefore, the overall time complexity is O(n log n).

Space Complexity

O(N) – The brute force approach, as described, iterates from 0 to N (inclusive), where N is the input number. For each number in this range, it calculates the number of set bits and stores this count. Thus, it implicitly maintains a list or array of size N+1 (from 0 to N) to store the counts of '1's for each number. This implies auxiliary space directly proportional to the input N, leading to O(N) space complexity.

Optimal Solution

Approach

The key is to notice a pattern in how the number of set bits changes as numbers increase. We can reuse previously calculated results to efficiently determine the number of set bits for each new number.

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

Think about small numbers first. The number zero has zero set bits, and the number one has one set bit.
Now, for any number, realize that it's related to a smaller number. For example, an even number's set bits are the same as half that number. That's because shifting right (dividing by two) doesn't change the number of set bits in an even number.
For an odd number, its set bits are one more than half the number before it (the even number directly below it). The extra one comes from the last bit being set to one in odd numbers.
So, for each number, use this relationship to find its set bits based on a number you've already calculated. Start from the beginning and build up your answer one number at a time.

Code Implementation

def counting_bits(number): 
    result_array = [0] * (number + 1)

    # Base case: 0 has zero set bits.
    result_array[0] = 0

    for index in range(1, number + 1):

        # Even numbers have the same number of set bits as half themselves.
        if index % 2 == 0:
            result_array[index] = result_array[index // 2]

        # Odd numbers have one more set bit than the even number before them.
        else:
            result_array[index] = result_array[index // 2] + 1

    return result_array

Big(O) Analysis

Time Complexity

O(n) – The algorithm iterates through numbers from 0 to n. For each number, it performs a single operation to determine the number of set bits based on a previously calculated value. This operation involves a division by 2 and a possible addition. Since the loop iterates n times and each iteration takes constant time, the overall time complexity is O(n).

Space Complexity

O(N) – The algorithm uses a list (or array) to store the count of set bits for each number from 0 to n. The plain English explanation implies building up the answer in this manner, requiring storage for each calculated bit count. Therefore, the auxiliary space used is proportional to the input number n. The space complexity is O(N) because we store n+1 integers.

Edge Cases

Case	How to Handle
Input n is zero	Return an array containing only zero, representing the count of bits for 0
Input n is a large number near the maximum integer value	Check for integer overflow to prevent incorrect results with dynamic programming or bit manipulation techniques
Input n is negative	The problem statement does not specify how to handle negative numbers, so explicitly return an error or define the behaviour as counting bits of the two's complement representation
n equals 1	Return an array containing [0, 1], which are the bit counts for 0 and 1
Values near power of 2, such as 2^k -1 or 2^k + 1	Ensure the algorithm correctly computes the bit counts in these potentially boundary conditions using bit manipulation
Maximum sized input (n = MAX_INT)	Consider space and time complexity; dynamic programming could use a large array, and bit manipulation should still be efficient
Integer Overflow during intermediate calculations	Carefully choose data types and operations to avoid exceeding the maximum representable integer value during any intermediate calculation.
n equals 2	Return an array containing [0, 1, 1], which are the bit counts for 0, 1 and 2.

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 non-negative integer limit for `n`? Specifically, what is the maximum possible value of `n`?
Should I return an array of length `n + 1` where `result[i]` represents the number of set bits in the binary representation of `i`?
Are there any specific memory constraints I should be aware of?
Is `n` guaranteed to be a non-negative integer, or should I handle invalid input types (e.g., null, negative numbers, strings)?
For the purpose of this problem, is the definition of 'set bits' universally understood to mean the count of bits that are 1 in the binary representation of an integer?

Brute Force Solution

Approach

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

Start with the first number in the range (which is zero).
Figure out how many '1's are in the binary representation of that number.
Record this count of '1's.
Move to the next number.
Again, figure out how many '1's are in the binary representation of that number.
Record this count of '1's.
Repeat this process for every number in the range, counting the '1's in each one and saving the result.
When you're done with all the numbers, you'll have a list of counts representing the number of '1's in each number from zero to the end of the range.

Code Implementation

def counting_bits_brute_force(number_range):    results = []
    # Iterate through each number in the range. 
    for number in range(number_range + 1):
        binary_representation = bin(number)[2:]
        bit_count = 0
        # Count the number of '1' bits. Necessary for the problem statement.
        for bit in binary_representation:
            if bit == '1':
                bit_count += 1

        results.append(bit_count)
    return results

Big(O) Analysis

Time Complexity

Space Complexity

Optimal Solution

Approach

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

Think about small numbers first. The number zero has zero set bits, and the number one has one set bit.
Now, for any number, realize that it's related to a smaller number. For example, an even number's set bits are the same as half that number. That's because shifting right (dividing by two) doesn't change the number of set bits in an even number.
For an odd number, its set bits are one more than half the number before it (the even number directly below it). The extra one comes from the last bit being set to one in odd numbers.
So, for each number, use this relationship to find its set bits based on a number you've already calculated. Start from the beginning and build up your answer one number at a time.

Code Implementation

def counting_bits(number): 
    result_array = [0] * (number + 1)

    # Base case: 0 has zero set bits.
    result_array[0] = 0

    for index in range(1, number + 1):

        # Even numbers have the same number of set bits as half themselves.
        if index % 2 == 0:
            result_array[index] = result_array[index // 2]

        # Odd numbers have one more set bit than the even number before them.
        else:
            result_array[index] = result_array[index // 2] + 1

    return result_array

Big(O) Analysis

Time Complexity

Space Complexity

Edge Cases

Case	How to Handle
Input n is zero	Return an array containing only zero, representing the count of bits for 0
Input n is a large number near the maximum integer value	Check for integer overflow to prevent incorrect results with dynamic programming or bit manipulation techniques
Input n is negative	The problem statement does not specify how to handle negative numbers, so explicitly return an error or define the behaviour as counting bits of the two's complement representation
n equals 1	Return an array containing [0, 1], which are the bit counts for 0 and 1
Values near power of 2, such as 2^k -1 or 2^k + 1	Ensure the algorithm correctly computes the bit counts in these potentially boundary conditions using bit manipulation
Maximum sized input (n = MAX_INT)	Consider space and time complexity; dynamic programming could use a large array, and bit manipulation should still be efficient
Integer Overflow during intermediate calculations	Carefully choose data types and operations to avoid exceeding the maximum representable integer value during any intermediate calculation.
n equals 2	Return an array containing [0, 1, 1], which are the bit counts for 0, 1 and 2.