algoadvance

Leetcode 1356. Sort Integers by The Number of 1 Bits

Problem Statement

Given an integer array arr, you need to sort it in non-decreasing order based on 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 should sort them in ascending order.

Clarifying Questions

1. Input Range: What is the range of integers in the array?
   • The array arr contains integers where 1 <= arr.length <= 500 and 0 <= arr[i] <= 10^4.
2. Return Type: What will the function return?
   • The function will return a new array sorted based on the given conditions.
3. Edge Cases: Should I consider edge cases like an empty array?
   • Yes, however since the problem guarantees 1 <= arr.length, we will not encounter an empty array.
4. Duplicate Elements: Can there be duplicate elements in the array?
   • Yes, duplicate elements can exist in the array and they should be treated according to the sorting rules.

Strategy

To solve this problem, you can follow these steps:

1. Custom Sort: Use a custom comparator to sort the array.
   • First, calculate the number of 1’s for each integer in the binary representation.
   • If two numbers have the same number of 1’s, sort them in ascending order.
2. Helper Function: Write a helper function to count the number of 1’s in the binary representation of a number.
3. STL Sort: Use the standard template library (STL) sort function with the custom comparator.

Code

Here is a C++ solution to the problem:

#include <vector>
#include <algorithm>

class Solution {
public:
    // Helper function to count number of 1's in binary representation of n
    int countOnes(int n) {
        int count = 0;
        while (n) {
            n &= (n - 1); // Drop the lowest set bit
            count++;
        }
        return count;
    }

    std::vector<int> sortByBits(std::vector<int>& arr) {
        // Custom comparator
        auto comparator = [this](int a, int b) {
            int countA = countOnes(a);
            int countB = countOnes(b);
            // If the number of 1's is the same, sort by the numbers themselves
            if (countA == countB)
                return a < b;
            // Otherwise, sort by the number of 1's
            return countA < countB;
        };
        
        // Use std::sort with the custom comparator
        std::sort(arr.begin(), arr.end(), comparator);
        return arr;
    }
};

Time Complexity

• Counting 1s: The helper function countOnes has a time complexity of O(log n) for each number since it operates on the binary representation of integers (which takes log(k) time where k is the value of the integer).
• Sorting: The std::sort function has a time complexity of O(n log n), where n is the number of elements in the array. For each comparison done by std::sort, it calls the comparator function which takes O(log k) (due to countOnes).

Combining these, the overall time complexity is:

• Worst Case: O(n log n * log k), where n is the size of the array and k is the maximum number in the array.

This should be efficient given the constraints.

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?