algoadvance

Leetcode 1356. Sort Integers by The Number of 1 Bits

Problem Statement

Given an integer array arr, you need to sort the integers in the array in ascending order by the number of 1s in their binary representation and in case of two or more integers have the same number of 1s you need to sort them in ascending order of their values.

Example:

1. Input: arr = [0,1,2,3,4,5,6,7,8]
   • Output: [0,1,2,4,8,3,5,6,7]
   • Explanation:
     • The numbers in binary are:
       • 0 -> 0000
       • 1 -> 0001
       • 2 -> 0010
       • 3 -> 0011
       • 4 -> 0100
       • 5 -> 0101
       • 6 -> 0110
       • 7 -> 0111
       • 8 -> 1000
     • Sorting by the number of 1s gives us [0, 1, 2, 4, 8, 3, 5, 6, 7].
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:
     • Binary representation has only one 1 bit for each number.

Clarifying Questions

1. Q: Should we consider negative numbers or just non-negative integers?
   • A: The problem typically involves non-negative integers.
2. Q: Are duplicates allowed in the array?
   • A: Yes, duplicates are allowed in the input array.
3. Q: Should the function be case-sensitive with regards to sorting?
   • A: Sorting is based on binary representation 1 bits and then by numeric value in case of ties.

Strategy

1. Convert each integer to its binary representation, count the number of 1 bits.
2. Sort the array using a custom comparator:
   • First, by the number of 1 bits.
   • Second, by the numeric value in case of ties.
3. Return the sorted array.

Using Java, we will:

• Implement a comparator that counts 1 bits using Integer.bitCount.
• Sort the array using Arrays.sort with the custom comparator.

Time Complexity

• Sorting: The time complexity of Arrays.sort() is O(n log n), where n is the number of elements in the array.
• Counting bits: Counting 1 bits using Integer.bitCount is O(1) since it processes a constant number of bits.

Java Code

import java.util.Arrays;

public class Solution {
    public int[] sortByBits(int[] arr) {
        // Sorting the array with a custom comparator
        Arrays.sort(arr, (a, b) -> {
            int bitCountA = Integer.bitCount(a);
            int bitCountB = Integer.bitCount(b);

            if (bitCountA == bitCountB) {
                return a - b; // If counts are equal, sort by the numeric value
            } else {
                return bitCountA - bitCountB; // Else sort by the bit count
            }
        });
        return arr;
    }

    public static void main(String[] args) {
        Solution sol = new Solution();
        
        // Test cases
        int[] arr1 = {0,1,2,3,4,5,6,7,8};
        System.out.println(Arrays.toString(sol.sortByBits(arr1))); // [0, 1, 2, 4, 8, 3, 5, 6, 7]

        int[] arr2 = {1024, 512, 256, 128, 64, 32, 16, 8, 4, 2, 1};
        System.out.println(Arrays.toString(sol.sortByBits(arr2))); // [1, 2, 4, 8, 16, 32, 64, 128, 256, 512, 1024]
    }
}

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI

• Got blindsided by a question you didn’t expect?

• Spend too much time studying?

• Or simply don’t have the time to go over all 3000 questions?