Problem

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.

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.

Solution

Video explanation

Here is the video explaining below methods in detail. Please check it out:

Method 1 - Bubble Sort

  1. Count set bits for each pair of adjacent elements.
  2. Swap adjacent elements if they have the same number of set bits and are not in the correct order.
  3. Repeat the process similar to bubble sort until no swaps are needed.
  4. Compare the modified array to the sorted array.
  5. Return true if they match, else false.

Code

Java
public class Solution {
    public boolean canSortArray(int[] nums) {
        int n = nums.length;
        
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n - 1; j++) {
                if (Integer.bitCount(nums[j]) == Integer.bitCount(nums[j + 1]) && nums[j] > nums[j + 1]) {
                    int temp = nums[j];
                    nums[j] = nums[j + 1];
                    nums[j + 1] = temp;
                }
            }
        }
        
        int[] sortedNums = Arrays.copyOf(nums, nums.length);
        Arrays.sort(sortedNums);
        
        return Arrays.equals(nums, sortedNums);
    }
}
Python
class Solution:
    def canSortArray(self, nums: List[int]) -> bool:
        def count_set_bits(x: int) -> int:
            return bin(x).count('1')
        
        n = len(nums)
        
        for i in range(n):
            for j in range(n - 1):
                if count_set_bits(nums[j]) == count_set_bits(nums[j + 1]) and nums[j] > nums[j + 1]:
                    nums[j], nums[j + 1] = nums[j + 1], nums[j]
        
        return nums == sorted(nums)

Complexity

  • ⏰ Time complexity: O(n^2 * log k), where k is the maximum number in the array.
  • 🧺 Space complexity: O(n), for storing a copy of the sorted array.

Method 2 - Group by bits

Another way can be to group the sorted array by bits, and then sort those individual groups, and attach the sorted bits and see if the array is sorted.

Method 3 - Comparing previous max of each group

The numbers can be grouped with other contiguous numbers with the same bit count. Once the bit count differs, you can mark the max value for the previous group. As long as any new numbers do not dip lower than the previous group’s max, the numbers processed thus far can be sorted. If any new number dips below the previous group’s max, we know we cannot sort the array according to the restrictions. This ensures that all numbers within each group and between groups are correctly sorted.

Code

Java
public class Solution {
    public boolean canSortArray(int[] nums) {
        int prevGroupMax = 0;
        int max = nums[0];
        
        for (int i = 1; i < nums.length; i++) {
            boolean bitChange = Integer.bitCount(max) != Integer.bitCount(nums[i]);
            if (bitChange) {
                prevGroupMax = max;
            }
            if (nums[i] > max) {
                max = nums[i];
            }
            if (nums[i] < prevGroupMax) {
                return false;
            }
        }
        return true;
    }
}
Python
class Solution:
    def canSortArray(self, nums: List[int]) -> bool:
        def count_bits(x: int) -> int:
            return bin(x).count('1')
        
        prev_group_max = 0
        max_val = nums[0]

        for i in range(1, len(nums)):
            bit_change = count_bits(max_val) != count_bits(nums[i])
            if bit_change:
                prev_group_max = max_val
            if nums[i] > max_val:
                max_val = nums[i]
            if nums[i] < prev_group_max:
                return False
        
        return True

Complexity

  • ⏰ Time complexity: O(n log k)
    • Count the number of set bits (count_bits): This operation takes O(log k) where k is the maximum value in the array since the number of bits is proportional to the logarithm of the number.
    • Overall loop: The loop iterates through the nums array exactly once.
  • 🧺 Space complexity: O(1) as we use some variables here and there