Leetcode 3011

Questions

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

Solution

class Solution {
public:
    bool canSortArray(vector<int>& nums) {
        queue<pair<int, int>> sequence;
        int prev_amount = -1;
        int min_val = INT_MAX, max_val = INT_MIN;

        for (int i = 0; i < nums.size(); i++) {
            std::string binary = std::bitset<32>(nums[i]).to_string();
            int amount = count(binary.begin(), binary.end(), '1');

            if (amount != prev_amount && prev_amount != -1) {
                sequence.push({min_val, max_val});
                min_val = nums[i];
                max_val = nums[i];
            } else {
                min_val = min(min_val, nums[i]);
                max_val = max(max_val, nums[i]);
            }
            if (!sequence.empty() && nums[i] < sequence.back().second) {
                return false;
            }

            prev_amount = amount;
        }

        sequence.push({min_val, max_val});

        int prev_max = INT_MIN;
        while (!sequence.empty()) {
            auto [group_min, group_max] = sequence.front();
            sequence.pop();
            if (group_min < prev_max) {
                return false;
            }
            prev_max = group_max;
        }

        return true;
    }
};

My approach can be not efficient because of the queue and the bit operation. I couldn’t find a better way to get a binary representation of a number.

I checked the minimum and maximum value of the group, and if the current value is less than the previous maximum value, the array cannot be sorted.

Then, I checked if the minimum value of the current group is less than the previous maximum value. If it is, the array cannot be sorted.

For example, If there’s numbers like 8, 4, 2, 30, 15, I seperately find minimum and maximum from 8, 4, 2 and 30, 15. 8, 4, 2 has minimum 2 and maximum 8, and 30, 15 has minimum 15 and maximum 30.

Then, I check if 2 < 8 and 15 < 8 is false, so the array can be sorted.