Sort Integers by The Number of 1 Bits - Practice Coding Problems

Sort Integers by The Number of 1 Bits - Problem

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.

In case of two or more integers have the same number of 1's, you have to sort them in ascending order by their decimal values.

Return the array after sorting it.

Input & Output

Example 1 — Basic Case

$ Input: arr = [0,1,1,2]

› Output: [0,1,1,2]

💡 Note: 0 has 0 bits, 1 has 1 bit each, 2 has 1 bit. Sorting by bit count: [0] (0 bits), then [1,1,2] (1 bit each, sorted by value)

Example 2 — Multiple Same Bit Counts

$ Input: arr = [1,5,3,7]

› Output: [1,3,5,7]

💡 Note: All have same bit count (1=1 bit, 5=2 bits, 3=2 bits, 7=3 bits). First 1 (1 bit), then 3,5 (2 bits, sorted by value), then 7 (3 bits)

Example 3 — Edge Case with Zero

$ Input: arr = [0,8,4,2,1]

› Output: [0,1,2,4,8]

💡 Note: 0 has 0 bits, 1,2,4,8 each have 1 bit. Result: 0 first, then 1,2,4,8 sorted by value

Constraints

1 ≤ arr.length ≤ 500
0 ≤ arr[i] ≤ 10⁴

Visualization

Tap to expand

Understanding the Visualization

Input Array

Original array: [0,1,1,2]

Count 1-bits

0→0 bits, 1→1 bit, 1→1 bit, 2→1 bit

Sorted Output

Sort by bit count, then by value: [0,1,1,2]

Key Takeaway

🎯 Key Insight: Use custom sorting with bit count as primary key and original value as secondary key

Asked in

a Amazon 15 M Microsoft 12 Apple 8

The key insight is to use a custom sorting comparator that first compares by number of 1-bits, then by original value. Best approach uses built-in sort with bit counting functions. Time: O(n log n), Space: O(log n)

Common Approaches

Approach	Time	Space	Notes
✓ Two-Pass with Precomputed Bit Counts	O(n log M + n log n)	O(n)	Precompute all bit counts once, then sort using the cached values
Built-in Sort with Custom Comparator	O(n log n × log M)	O(log n)	Use built-in sorting with custom comparison function that counts bits efficiently
Brute Force with Manual Bit Counting	O(n² × log M)	O(1)	Count 1-bits manually for each number, then sort using nested loops

Two-Pass with Precomputed Bit Counts — Algorithm Steps

Step 1: Create array/map to store bit count for each number
Step 2: Calculate bit counts once for all numbers
Step 3: Sort using precomputed bit counts as keys

Visualization

Tap to expand

Step-by-Step Walkthrough

Precompute

Calculate all bit counts in first pass

Cache

Store bit counts to avoid recalculation

Sort

Use cached bit counts for efficient sorting

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

struct Element {
    int value;
    int bitCount;
};

int countBits(int n) {
    int count = 0;
    while (n) {
        count++;
        n &= n - 1;
    }
    return count;
}

int compare(const void* a, const void* b) {
    struct Element* x = (struct Element*)a;
    struct Element* y = (struct Element*)b;
    if (x->bitCount != y->bitCount) {
        return x->bitCount - y->bitCount;
    }
    return x->value - y->value;
}

void solution(int* arr, int size) {
    struct Element* elements = malloc(size * sizeof(struct Element));
    
    // Precompute bit counts
    for (int i = 0; i < size; i++) {
        elements[i].value = arr[i];
        elements[i].bitCount = countBits(arr[i]);
    }
    
    // Sort using precomputed counts
    qsort(elements, size, sizeof(struct Element), compare);
    
    // Copy back to original array
    for (int i = 0; i < size; i++) {
        arr[i] = elements[i].value;
    }
    
    free(elements);
}

int main() {
    char line[10000];
    fgets(line, sizeof(line), stdin);
    
    int arr[1000];
    int size = 0;
    char* token = strtok(line, "[,]");
    while (token != NULL) {
        if (strlen(token) > 0 && token[0] != ' ' && token[0] != '\n') {
            arr[size++] = atoi(token);
        }
        token = strtok(NULL, "[,]");
    }
    
    solution(arr, size);
    
    printf("[");
    for (int i = 0; i < size; i++) {
        printf("%d", arr[i]);
        if (i < size - 1) printf(",");
    }
    printf("]\n");
    
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n log M + n log n)

First pass O(n log M) for bit counting + sorting O(n log n)

⚡ Linearithmic

Space Complexity

O(n)

Extra array to store bit counts for each element

⚡ Linearithmic Space

64.6K Views

Medium Frequency

~15 min Avg. Time

1.8K Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Two-Pass with Precomputed Bit Counts — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler