Find if Array Can Be Sorted

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 in ascending order, else return false.

Example 1:

Input: nums = [8,4,2,30,15]
Output: true

Example 2:

Input: nums = [1,2,3,4,5]
Output: true

Example 3:

Input: nums = [3,16,8,4,2]
Output: false

Constraints:

• 1 <= nums.length <= 100
• 1 <= nums[i] <= 2^8

def can_sort_array(nums):
    """Determines if an array can be sorted by swapping adjacent elements with the same number of set bits."""
    n = len(nums)
    arr = [(bin(num).count('1'), num) for num in nums]

    for i in range(n):
        for j in range(n - i - 1):
            if arr[j][0] == arr[j+1][0] and arr[j][1] > arr[j+1][1]:
                arr[j], arr[j+1] = arr[j+1], arr[j]

    sorted_nums = [num for _, num in arr]
    return sorted_nums == sorted(nums)

# Example Usage:
nums1 = [8, 4, 2, 30, 15]
print(f"Input: {nums1}, Output: {can_sort_array(nums1)}")  # Output: True

nums2 = [1, 2, 3, 4, 5]
print(f"Input: {nums2}, Output: {can_sort_array(nums2)}")  # Output: True

nums3 = [3, 16, 8, 4, 2]
print(f"Input: {nums3}, Output: {can_sort_array(nums3)}")  # Output: False

Explanation:

1. can_sort_array(nums) Function:
   • Takes a list of positive integers nums as input.
   • Calculates the number of set bits (1s in binary representation) for each number and stores it along with the original number in a list of tuples called arr. This is done using a list comprehension: arr = [(bin(num).count('1'), num) for num in nums]
   • Performs a bubble sort-like iteration to sort the array based on the problem's condition: adjacent elements with the same number of set bits can be swapped if they are out of order.
   • After the sorting process, extracts the numbers from the sorted arr to get sorted_nums. Checks if sorted_nums is equal to the ascending sorted version of original nums. Returns True if they are the same, else False.

Big(O) Analysis:

• Time Complexity: O(n²)
  • The outer loop runs n times (where n is the length of nums).
  • The inner loop also runs close to n times in the worst case.
  • Hence, the overall time complexity is dominated by the nested loops, resulting in O(n²).
  • Calculating the number of set bits for each number takes O(n) time in total (as bin(num).count('1') is O(1) since the integers are limited to a maximum of 8 bits as per the constraints).
  • Sorting the array at the end takes O(n log n) time. However, this is dominated by the nested loops. This bubble-sort like algorithm is done inplace.
• Space Complexity: O(n)
  • The arr list stores tuples containing set bit counts and original numbers, using O(n) space.
  • sorted_nums also requires O(n) space to store the sorted numbers.
  • Therefore, the overall space complexity is O(n).

Edge Cases:

1. Empty Input:

   • If the input list nums is empty, the function will still work correctly because the loops won't execute, and it will return True (since an empty list is considered sorted).

2. Already Sorted Array:

   • If the input array is already sorted, the inner loops won't make any swaps, and the function will return True efficiently.

3. Array with Identical Elements:

   • If the array contains identical elements (e.g., [2, 2, 2, 2]), the function will also return True because it's already considered sorted.

4. Array with Numbers Having Same Number of Set Bits but Cannot Be Sorted:

   • An example is [3, 16, 8, 4, 2]. 3 has two set bits, 16, 8, 4, and 2 have one set bit. Numbers with one set bit can be rearranged between each other. The algorithm will correctly return False because even after optimally rearranging the numbers with one set bit, we can't sort the array.

5. Large Input Array:

   • The algorithm's O(n²) time complexity might be a concern for very large input arrays (approaching the constraint limit of 100). However, the constraints are small enough that an O(n²) solution is acceptable.