Find if Array Can Be Sorted

Problem Statement

The task is based on manipulating a given array of positive integers named nums, which is structured in a 0-indexed format. The core operation allowed in this scenario is swapping any two adjacent elements of the array, but the condition for such a swap is that both elements must contain the same number of 1's in their binary representation. This operation can be repeated numerous times, including not performing any swaps at all.

The primary objective is to determine if it is possible to sort the array in ascending order using the above-defined operation. The result should be returned as true if the array can be sorted in that manner, or false otherwise.

Examples

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

Approach and Intuition

The primary intuition here revolves around understanding the binary representation of numbers—particularly, the count of set bits (1's).

• Each example elucidates different scenarios:

  • Example 1:

    • Input: nums = [8,4,2,30,15]
    • The numbers (2, 4, 8) have one set bit each, allowing swaps among them. Similarly, the numbers (30, 15) with four set bits each can be rearranged amongst themselves. The allowable manipulations enable sorting of the entire array, returning true.

  • Example 2:

    • Input: nums = [1,2,3,4,5]
    • This example forms a naturally sorted array from the outset, thus avoiding the need for any operations, returning true.

  • Example 3:

    • Input: nums = [3,16,8,4,2]
    • Despite different possibilities of swaps for numbers with the same set bits, it's impossible to fully sort the entire sequence in ascending order due to the mixed distribution of set bits that isolate some numbers (like 3 with two set bits). Here, swapping alone based on set bits constraint cannot yield a sorted array, so it returns false.

From observing the given examples, the strategy broadly hints at checking if:

1. Grouping numbers by their set bit counts can be sorted independently.
2. Post group sorting, if these grouped numbers themselves form an ascending sequence based on their minimum and maximum values, ensuring a globally sorted structure.

Understanding the constraints where the length of the array (nums.length) can go up to 100 and each element's value (nums[i]) ranges from 1 to 28 also implies that efficient manipulation and checks can be managed within these bounds.

Solutions

class Solution {
public:
    bool isSortable(vector<int>& elements) {
        int size = elements.size();
        vector<int> copiedElements = elements;
    
        for (int i = 0; i < size - 1; i++) {
            if (copiedElements[i] <= copiedElements[i + 1]) {
                continue;
            } else {
                if (__builtin_popcount(copiedElements[i]) == __builtin_popcount(copiedElements[i + 1])) {
                    swap(copiedElements[i], copiedElements[i + 1]);
                } else {
                    return false;
                }
            }
        }
    
        for (int i = size - 1; i >= 1; i--) {
            if (copiedElements[i] >= copiedElements[i - 1]) {
                continue;
            } else {
                if (__builtin_popcount(copiedElements[i]) == __builtin_popcount(copiedElements[i - 1])) {
                    swap(copiedElements[i], copiedElements[i - 1]);
                } else {
                    return false;
                }
            }
        }
    
        return true;
    }
};