We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Sort Integers by The Number of 1 Bits

Number: 1458

Difficulty: Easy

Paid? No

Companies: Google, J.P. Morgan, Accenture, Goldman Sachs

Problem Description

Given an integer array, sort the numbers in ascending order by the count of 1's in their binary representation. If two numbers have the same number of 1's, they should be sorted in ascending numerical order.

Key Insights

  • Count the number of 1 bits in the binary representation of each integer.
  • Use a sorting algorithm that utilizes a custom key: a tuple (bit count, integer value).
  • For integers with equal bit counts, ensure natural ascending order.

Space and Time Complexity

Time Complexity: O(n log n) due to sorting (the bit count operation is O(1) for bounded integer sizes).
Space Complexity: O(n) if additional space is used for sorting, otherwise O(1) for in-place sorts.

Solution

The solution computes the number of 1 bits for each integer and sorts the array based on a composite key made up of the bit count and the integer itself. The sorting is stable and ensures that if two integers share the same number of bits, they are ordered by their natural numerical value. We use built-in functions for counting bits (such as bin(x).count("1") in Python or Integer.bitCount in Java), and customized sorting logic in each language.

Code Solutions

def sort_by_bits(arr):
    # Sort the array using a tuple (popcount, number)
    # bin(x).count("1") returns the number of '1's in the binary representation of x.
    return sorted(arr, key=lambda x: (bin(x).count("1"), x))

# Example usage
if __name__ == "__main__":
    arr = [0,1,2,3,4,5,6,7,8]
    print(sort_by_bits(arr))
← Back to All Questions