Skip to main content

1356. Sort Integers by The Number of 1 Bits

easy

Sort an integer array primarily by popcount ascending, breaking ties by value. A clean pair-key custom-sort: (popcount(x), x).

By Alex Chen, Founder, InterviewChamp.AI · Last verified

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 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.

Constraints

  • 1 <= arr.length <= 500
  • 0 <= arr[i] <= 10^4

Examples

Example 1

Input
arr = [0,1,2,3,4,5,6,7,8]
Output
[0,1,2,4,8,3,5,6,7]

Explanation: [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]

Explanation: All integers have 1 bit in the binary representation, you should just sort them in ascending order.

Solve it now

Free. No sign-up. Python and JavaScript run instantly in your browser.

Output

Press Run or Cmd+Enter to execute

Hints

Progressive — try the first before opening the next.

Hint 1

Use a comparator that returns (popcount(x), x) as a tuple — most languages sort lexicographically on tuples by default.

Hint 2

Or encode the comparison key into one int: (popcount(x) << 14) | x — popcount fits in 5 bits, x fits in 14 bits given arr[i] <= 10^4 < 2^14.

Hint 3

Use any popcount routine: Integer.bitCount in Java, bin(x).count('1') in Python, __builtin_popcount in C++.

Solution approach

Reveal approach

Custom-key sort. Sort arr in place with key = (popcount(x), x): primary key is set-bit count ascending, secondary key is the integer value ascending. Python: arr.sort(key=lambda x: (bin(x).count('1'), x)). Java: Arrays.sort(arr_boxed, (a, b) -> { int da = Integer.bitCount(a), db = Integer.bitCount(b); return da != db ? da - db : a - b; }). C++ similar via a lambda passed to std::sort. With n <= 500 the sort is essentially free. O(n log n) time, O(1) extra space (if sorting in-place — Java requires boxing to use a comparator).

Complexity

Time
O(n log n)
Space
O(1)

Related patterns

  • bit-manipulation
  • sorting

Related problems

Asked at

Companies reported asking this problem (sourced from public Glassdoor, Blind, and Levels.fyi interview posts).

  • Microsoft

Practice these live with InterviewChamp.AI

Drill Sort Integers by The Number of 1 Bits and Bit Manipulation problems under real interview conditions with instant feedback on your reasoning, complexity claims, and code.

Practice these live with InterviewChamp.AI →