Teaching Kids Programming – Sort List by Hamming Weight

Teaching Kids Programming: Videos on Data Structures and Algorithms

You are given a lists of non-negative integers nums. Sort the list in ascending order by the number of 1s in binary representation for each number. If there are ties in the number of 1s, then break ties by their value in ascending order.

Constraints
0 ≤ n ≤ 100,000 where n is the length of nums
Example 1
Input
nums = [3, 1, 4, 7]
Output
[1, 4, 3, 7]
Explanation
1 and 4 both have one 1s but 1 comes earlier since it has lower value. 3 has two 1s. And 7 has three 1s.

Sort List by Hamming Weight

The Hamming Weight of a Integer is the number of ones in its binary representation:

We can use the bin function to convert a integer to binary string prefixed with ‘0b’ e.g. ‘0b1111’ for 15. Then we can use the count function to simply count the character ‘1’. This takes O(logN.logN) time complexity.

1
2

def hammingWeight(n):
  return bin(n).count('1')

def hammingWeight(n):
  return bin(n).count('1')

We can count the 1’s in a much efficient manner, removing right-most 1 (least significant 1) at a time:

1
2
3
4
5
6

def hammingWeight(n):
  ans = 0
  while n:
    ans += 1
    n &= n - 1
  return ans

def hammingWeight(n):
  ans = 0
  while n:
    ans += 1
    n &= n - 1
  return ans

This is going to take O(LogN) time. However, if the input number is bounded to 32-bit integer, the time complexity is O(1) constant as it takes at most 32 iterations. Another bit algorithm is to check 1 digit at a time and remove it:

1
2
3
4
5
6

def hammingWeight(n):
  ans = 0
  while n:
    ans += n & 1
    n >>= 1
  return ans

def hammingWeight(n):
  ans = 0
  while n:
    ans += n & 1
    n >>= 1
  return ans

We then can specify the hamming function as the key in either sort() or sorted():

1
2
3
4
5
6
7

class Solution:
    def sortByHammingWeight(self, nums):
        if not nums:
            return []
        # return sorted(nums, key=lambda x: (hammingWeight(x), x))
        nums.sort(key=lambda x: (hammingWeight(x), x))
        return nums

class Solution:
    def sortByHammingWeight(self, nums):
        if not nums:
            return []
        # return sorted(nums, key=lambda x: (hammingWeight(x), x))
        nums.sort(key=lambda x: (hammingWeight(x), x))
        return nums

The key returns a tuple first is the hamming weight and in case there is a tie, sorted by the value. The time complexity is O(NLogN).

Hamming Weight / Hamming Distance Algorithms

Here are the posts related to Hamming Distance (XOR, The number of different bits):

• A faster approach to count set bits in a 32-bit integer
• Teaching Kids Programming – Minimum Bit Flips to Convert Number (Hamming Distance)
• GoLang: Compute the Hamming Distance
• How to Sort List by Hamming Weight in C++?
• Teaching Kids Programming – Compute the Hamming Distance of Two Integers
• Compute the Total Hamming Distance between All Pairs of Integers
• The Hamming Distance Implementation in Javascript
• Hamming Distance between Two Integers
• Compute Number of 1’s Bits in C/C++
• Teaching Kids Programming – Sort List by Hamming Weight

–EOF (The Ultimate Computing & Technology Blog) —