Ideas from Selection Sort

Selection Sort is a common N^2 sorting technique with the following based premise: find the minimum element of an array (O(N)), move it to be the first. Repeat this for the remaining elements (O(N), hence the total is N^2). In this problem we can use the exact same idea, the only variation is that you need to pre-compute the number-to-countBits for every number, and ensure that the path to move the element to becoming the first adheres to the problem statement (along the way all the numbers need to have the same number of Bits, which you can then make use of the pre-computed map). Code is down below, cheers, ACC.

Find if Array Can Be Sorted - LeetCode

3011. Find if Array Can Be Sorted

Medium

You are given a 0-indexed array of positive integers nums.

In one operation, you can swap any two adjacent elements if they have the same number of set bits. You are allowed to do this operation any number of times (including zero).

Return true if you can sort the array, else return false.

 

Example 1:

Input: nums = [8,4,2,30,15]
Output: true
Explanation: Let's look at the binary representation of every element. The numbers 2, 4, and 8 have one set bit each with binary representation "10", "100", and "1000" respectively. The numbers 15 and 30 have four set bits each with binary representation "1111" and "11110".
We can sort the array using 4 operations:
- Swap nums[0] with nums[1]. This operation is valid because 8 and 4 have one set bit each. The array becomes [4,8,2,30,15].
- Swap nums[1] with nums[2]. This operation is valid because 8 and 2 have one set bit each. The array becomes [4,2,8,30,15].
- Swap nums[0] with nums[1]. This operation is valid because 4 and 2 have one set bit each. The array becomes [2,4,8,30,15].
- Swap nums[3] with nums[4]. This operation is valid because 30 and 15 have four set bits each. The array becomes [2,4,8,15,30].
The array has become sorted, hence we return true.
Note that there may be other sequences of operations which also sort the array.

Example 2:

Input: nums = [1,2,3,4,5]
Output: true
Explanation: The array is already sorted, hence we return true.

Example 3:

Input: nums = [3,16,8,4,2]
Output: false
Explanation: It can be shown that it is not possible to sort the input array using any number of operations.

 

Constraints:

• 1 <= nums.length <= 100
• 1 <= nums[i] <= 28

public class Solution {
    public bool CanSortArray(int[] nums)
    {
        Hashtable numberToSetBits = MapNumberSetBits(nums);

        List list = nums.ToList();
        while (list.Count > 0)
        {
            //Find min
            int min = Int32.MaxValue;
            int indexMin = -1;
            for (int i = 0; i < list.Count; i++)
            {
                if (list[i] < min)
                {
                    min = list[i];
                    indexMin = i;
                }
            }

            //Check
            for (int i = 0; i < indexMin; i++)
                if ((int)numberToSetBits[list[i]] != (int)numberToSetBits[list[indexMin]]) return false;

            //Remove
            list.RemoveAt(indexMin);
        }

        return true;
    }

    private Hashtable MapNumberSetBits(int[] nums)
    {
        Hashtable ht = new Hashtable();

        for (int i = 0; i < nums.Length; i++)
        {
            if (!ht.ContainsKey(nums[i]))
                ht.Add(nums[i], Convert.ToString(nums[i], 2).Where(c => c == '1').Count());
        }
        return ht;
    }
}