Sorting Array On Number Of Bits

Sort Integers in an Array by The Number of 1 Bits.

Problem Statement

 

You are given an array of integers, and you have to 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. Here is one example, array [ 5, 0, 7, 1, 2, 6, 3, 4, 8 ] would result to [ 0, 1, 2, 4, 8, 3, 5, 6, 7 ] since, [ 0 ] is the only integer with 0 bits, [ 1, 2, 4, 8 ] all have 1 bit, [ 3, 5, 6] have 2 bits and [ 7 ] has 3 bits. So, the sorted array by bits is [ 0, 1, 2, 4, 8, 3, 5, 6, 7 ]. Another example, array [ 1024, 512, 256, 128, 64, 32, 16, 8, 4, 2, 1 ] would result to [ 1, 2, 4, 8, 16, 32, 64, 128, 256, 512, 1024 ]. For more details, here is the link to the leetcode question.

 

Approach 1

 

One way to solve this problem is by using the custom comparer to sort the array. This approach needs no extra modules to sort the array (like Linq). A common method is defined to convert the decimal number to binary number and then count the number of 1's from that binary number. We used the System.Convert.ToString() to convert the decimal to binary rather then just dividing it by 2s. After counting the number of 1's in the binary representation of each integer, we will sort them by the number of 1's ascending and if two numbers have same 1's then we will compare by the value. Here is the C# code for the algorithm,

static void Main(string[] args)
{
    var array = new int[] { 5, 0, 7, 1, 2, 6, 3, 4, 8 };
    array.Approach1();
    // array is [ 0, 1, 2, 4, 8, 3, 5, 6, 7 ]
}
static void Approach1(this int[] array)
{
    Array.Sort(array, (x, y) =>
    {
        if (NumberOf1s(x).Equals(NumberOf1s(y)))
            return x.CompareTo(y);
        return NumberOf1s(x).CompareTo(NumberOf1s(y));
    });
}
static int NumberOf1s(int number)
{
    string binary = Convert.ToString(number, 2);
    return binary.Count(c => c.Equals('1'));
}

Approach 2

 

The most simple method of sorting the array is by using linq's OrderBy(). Hence, will need the reference to the module System.Linq. Firstly, we will order it on the basis of the number of 1s in the binary number of the decimal integer. And then, on the basis of its value. The psuedo code for this linq approach is given below,

static void Main(string[] args)
{
    var array = new int[] { 5, 0, 7, 1, 2, 6, 3, 4, 8 };
    var result = Approach2(array);
    // result is [ 0, 1, 2, 4, 8, 3, 5, 6, 7 ]
}
static int[] Approach2(this int[] array)
{
    return array.OrderBy(x =>
    {
        string binary = Convert.ToString(x, 2);
        return binary.Count(c => c.Equals('1'));
    }).ThenBy(x => x).ToArray();
}

Conclusion

 

Both will have the same time complexity, that is O(N*Log N) and O(N*N) in a worst case scenario since both the Array.Sort() and OrderBy() uses the quick sort algorithm to sort the given array. But the space complexity will differ, approach 1 will have a space complexity of O(1), since no extra space is consumed in order to sort the array. And in case of approach 2, we will have a space complexity of O(N), since the OrderBy() linq method will create a new IOrderedEnumerable<int> of the same length of the given array.