Jobs

Interviews

Discussions

Sort Integers by The Number of 1 Bits

Easy

Amazon

3 views

Topics:

ArraysBit Manipulation

You are given an integer array arr. Sort the integers in the array in ascending order by the number of 1's in their binary representation and in case of two or more integers have the same number of 1's you have to sort them in ascending order.

Return the array after sorting it.

Example 1:

Input: arr = [0,1,2,3,4,5,6,7,8]
Output: [0,1,2,4,8,3,5,6,7]
Explantion: [0] is the only integer with 0 bits.
[1,2,4,8] all have 1 bit.
[3,5,6] have 2 bits.
[7] has 3 bits.
The sorted array by bits is [0,1,2,4,8,3,5,6,7]

Example 2:

Input: arr = [1024,512,256,128,64,32,16,8,4,2,1]
Output: [1,2,4,8,16,32,64,128,256,512,1024]
Explantion: All integers have 1 bit in the binary representation, you should just sort them in ascending order.

Constraints:

1 <= arr.length <= 500
0 <= arr[i] <= 10⁴

Sort Integers by The Number of 1 Bits

Easy

Amazon

3 views

Topics:

ArraysBit Manipulation

Return the array after sorting it.

Example 1:

Input: arr = [0,1,2,3,4,5,6,7,8]
Output: [0,1,2,4,8,3,5,6,7]
Explantion: [0] is the only integer with 0 bits.
[1,2,4,8] all have 1 bit.
[3,5,6] have 2 bits.
[7] has 3 bits.
The sorted array by bits is [0,1,2,4,8,3,5,6,7]

Example 2:

Input: arr = [1024,512,256,128,64,32,16,8,4,2,1]
Output: [1,2,4,8,16,32,64,128,256,512,1024]
Explantion: All integers have 1 bit in the binary representation, you should just sort them in ascending order.

Constraints:

1 <= arr.length <= 500
0 <= arr[i] <= 10⁴

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 integer values within the input array `arr`? Are negative numbers possible?
What should I return if the input array `arr` is null or empty?
If two numbers have the same number of 1 bits, should I maintain their original relative order in the sorted output, or is ascending order strictly required regardless of their initial positions?
Can you provide an example of an input array and its expected sorted output to clarify the sorting criteria?
What is the maximum size of the input array `arr`? This will help me consider potential performance implications and choose appropriate algorithms.

Brute Force Solution

Approach

The brute force way to sort numbers by their 1-bits is pretty straightforward. We go through each number, count how many 1s it has, and then use that count to sort all the numbers.

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

For each number in the list, figure out how many 1s are in its binary representation. Imagine flipping the number into binary and counting the ones.
Store this count alongside its original number. So now each number has a partner: its 1-bit count.
Now, sort these number-count pairs based on the 1-bit counts. Put the ones with the fewest 1s first.
If two numbers have the same number of 1s, then sort those two numbers according to their original numerical value (smaller number comes first).
Finally, take out just the original numbers from the sorted pairs, leaving the 1-bit counts behind. This gives you the sorted list of numbers.

Code Implementation

def sort_by_one_bits_brute_force(numbers):
    number_with_bit_counts = []

    for number in numbers:
        # Calculate the number of 1 bits
        binary_representation = bin(number)[2:]
        number_of_set_bits = binary_representation.count('1')
        number_with_bit_counts.append((number, number_of_set_bits))

    # Sort based on number of 1 bits and then numerical value
    number_with_bit_counts.sort(key=lambda item: (item[1], item[0]))

    # Extract original numbers from the sorted pairs
    sorted_numbers = [number for number, _ in number_with_bit_counts]

    return sorted_numbers

Try it yourself on LeetCode

Big(O) Analysis

Time Complexity

O(n log n) – The algorithm iterates through n numbers to count the set bits in each, which takes O(n) time in total, assuming a constant time operation for counting bits of each number. Storing the numbers along with their bit counts takes O(n) space. The sorting step, which sorts the pairs based on the number of 1s and then the original value, dominates the time complexity. A typical efficient sorting algorithm like merge sort or quicksort would take O(n log n) time. Therefore, the overall time complexity is O(n log n).

Space Complexity

O(N) – The algorithm creates a list of number-count pairs, where each pair stores an original number and its corresponding 1-bit count. Since there is a pair for each of the N numbers in the input list, this auxiliary data structure requires space proportional to N. The sorting operation itself, depending on the implementation, might require additional space, but the dominant factor is the storage of the number-count pairs. Therefore, the space complexity is O(N).

Optimal Solution

Approach

To efficiently sort numbers by the count of '1's in their binary representation, we'll first count the number of '1's for each number. Then, we'll sort the numbers based on these counts, using the original number as a tiebreaker when counts are equal.

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

For each number in the list, figure out how many '1's are in its binary form. We're essentially counting how many bits are turned on.
Store this '1' count along with the original number. Think of it as creating a tag for each number that tells you how many '1's it has.
Now, sort the numbers based on these '1' counts. Numbers with fewer '1's will come first.
If two numbers have the same '1' count, sort them by their original numerical value (smaller numbers come first). This ensures a stable sort.
The result is a list of numbers sorted primarily by the number of '1's they have, and secondarily by their original values if the '1' counts are the same.

Code Implementation

def sort_by_bits(arr):
    def count_set_bits(number):
        count = 0
        while number > 0:
            number &= (number - 1)
            count += 1
        return count

    # Create a list of tuples: (bit_count, original_number)
    bit_counts_with_original_numbers = []
    for number in arr:
        bit_counts_with_original_numbers.append((count_set_bits(number), number))

    # Sort based on bit count, then original number
    bit_counts_with_original_numbers.sort(key=lambda item: (item[0], item[1]))

    # Extract the sorted original numbers
    sorted_array = [number for _, number in bit_counts_with_original_numbers]

    return sorted_array

Try it yourself on LeetCode

Big(O) Analysis

Time Complexity

O(n log n) – The algorithm iterates through each of the n numbers in the input array to count the number of set bits, which takes O(n) time in total assuming a bitwise operation is O(1). Then, the algorithm sorts the numbers based on the count of set bits. Sorting typically takes O(n log n) time using efficient comparison based sorting algorithms like merge sort or quicksort. Therefore, the overall time complexity is dominated by the sorting step, resulting in O(n log n).

Space Complexity

O(N) – The algorithm creates a temporary list or array to store each number along with its corresponding count of 1 bits. In the worst-case scenario, this list will contain all N numbers from the input list, where N is the size of the input. Therefore, the auxiliary space required scales linearly with the input size. This temporary storage dominates the space complexity, resulting in O(N) space.

Edge Cases

Case	How to Handle
Null or empty input array	Return an empty array or throw an IllegalArgumentException depending on the requirements.
Input array with a single element	Return the array itself as it is already sorted.
Input array with all elements being zero	The array should be returned as is, since all elements have zero 1-bits and are already in ascending order.
Input array with all elements having the same number of 1 bits	The array should be sorted in ascending order based on the integer values themselves.
Input array containing negative numbers	Handle negative numbers by considering their two's complement representation when counting 1-bits.
Input array with large integer values close to Integer.MAX_VALUE or Integer.MIN_VALUE	Ensure the bit counting algorithm doesn't overflow or have unexpected behavior with large values.
Input array with duplicate numbers having different numbers of 1 bits	The sorting should correctly place the duplicates based on their respective 1-bit counts and values.
Input array with extreme values and a mix of positive, negative, and zero integers	The solution should accurately count set bits and sort based on the specifications, accounting for all number types.

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 integer values within the input array `arr`? Are negative numbers possible?
What should I return if the input array `arr` is null or empty?
If two numbers have the same number of 1 bits, should I maintain their original relative order in the sorted output, or is ascending order strictly required regardless of their initial positions?
Can you provide an example of an input array and its expected sorted output to clarify the sorting criteria?
What is the maximum size of the input array `arr`? This will help me consider potential performance implications and choose appropriate algorithms.

Brute Force Solution

Approach

The brute force way to sort numbers by their 1-bits is pretty straightforward. We go through each number, count how many 1s it has, and then use that count to sort all the numbers.

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

For each number in the list, figure out how many 1s are in its binary representation. Imagine flipping the number into binary and counting the ones.
Store this count alongside its original number. So now each number has a partner: its 1-bit count.
Now, sort these number-count pairs based on the 1-bit counts. Put the ones with the fewest 1s first.
If two numbers have the same number of 1s, then sort those two numbers according to their original numerical value (smaller number comes first).
Finally, take out just the original numbers from the sorted pairs, leaving the 1-bit counts behind. This gives you the sorted list of numbers.

Code Implementation

def sort_by_one_bits_brute_force(numbers):
    number_with_bit_counts = []

    for number in numbers:
        # Calculate the number of 1 bits
        binary_representation = bin(number)[2:]
        number_of_set_bits = binary_representation.count('1')
        number_with_bit_counts.append((number, number_of_set_bits))

    # Sort based on number of 1 bits and then numerical value
    number_with_bit_counts.sort(key=lambda item: (item[1], item[0]))

    # Extract original numbers from the sorted pairs
    sorted_numbers = [number for number, _ in number_with_bit_counts]

    return sorted_numbers

Try it yourself on LeetCode

Big(O) Analysis

Time Complexity

Space Complexity

Optimal Solution

Approach

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

For each number in the list, figure out how many '1's are in its binary form. We're essentially counting how many bits are turned on.
Store this '1' count along with the original number. Think of it as creating a tag for each number that tells you how many '1's it has.
Now, sort the numbers based on these '1' counts. Numbers with fewer '1's will come first.
If two numbers have the same '1' count, sort them by their original numerical value (smaller numbers come first). This ensures a stable sort.
The result is a list of numbers sorted primarily by the number of '1's they have, and secondarily by their original values if the '1' counts are the same.

Code Implementation

def sort_by_bits(arr):
    def count_set_bits(number):
        count = 0
        while number > 0:
            number &= (number - 1)
            count += 1
        return count

    # Create a list of tuples: (bit_count, original_number)
    bit_counts_with_original_numbers = []
    for number in arr:
        bit_counts_with_original_numbers.append((count_set_bits(number), number))

    # Sort based on bit count, then original number
    bit_counts_with_original_numbers.sort(key=lambda item: (item[0], item[1]))

    # Extract the sorted original numbers
    sorted_array = [number for _, number in bit_counts_with_original_numbers]

    return sorted_array

Try it yourself on LeetCode

Big(O) Analysis

Time Complexity

Space Complexity

Edge Cases

Case	How to Handle
Null or empty input array	Return an empty array or throw an IllegalArgumentException depending on the requirements.
Input array with a single element	Return the array itself as it is already sorted.
Input array with all elements being zero	The array should be returned as is, since all elements have zero 1-bits and are already in ascending order.
Input array with all elements having the same number of 1 bits	The array should be sorted in ascending order based on the integer values themselves.
Input array containing negative numbers	Handle negative numbers by considering their two's complement representation when counting 1-bits.
Input array with large integer values close to Integer.MAX_VALUE or Integer.MIN_VALUE	Ensure the bit counting algorithm doesn't overflow or have unexpected behavior with large values.
Input array with duplicate numbers having different numbers of 1 bits	The sorting should correctly place the duplicates based on their respective 1-bit counts and values.
Input array with extreme values and a mix of positive, negative, and zero integers	The solution should accurately count set bits and sort based on the specifications, accounting for all number types.