> ## Documentation Index
> Fetch the complete documentation index at: https://leetcode-py.wisl.dev/llms.txt
> Use this file to discover all available pages before exploring further.

> ## Agent Instructions
> leetcode-py is a Python LeetCode practice environment generator with one CLI: lcpy. It is not a service or platform.
> Each problem is a directory under leetcode/ with README.md, solution.py, test_solution.py, helpers.py, and playground.ipynb. lcpy gen creates them from JSON templates bundled with the package.
> Examples are backed by tests; copy them verbatim.

# Find if Array Can Be Sorted Python Solution

> Tested Python solution for LeetCode 3011 with 18 pytest cases. Generate a practice environment with lcpy.

LeetCode 3011, [Medium](/catalog/medium). Topics: [Array](/catalog/topics/array), [Bit Manipulation](/catalog/topics/bit-manipulation), [Sorting](/catalog/topics/sorting). [View on LeetCode](https://leetcode.com/problems/find-if-array-can-be-sorted/description/).

Generate this problem as a practice environment: tested reference solution, 18 [parametrized pytest cases](/practice/testing), and a playground notebook:

```bash theme={"theme":{"light":"github-light","dark":"github-dark"}}
lcpy gen -n 3011   # by problem number
lcpy gen -s find_if_array_can_be_sorted   # by problem name
```

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

### Examples

```
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.
```

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

```
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] \<= 2^8

## Solution

Reference implementation from [solution.py on GitHub](https://github.com/wislertt/leetcode-py/blob/main/leetcode/find_if_array_can_be_sorted/solution.py), full suite in [test\_solution.py](https://github.com/wislertt/leetcode-py/blob/main/leetcode/find_if_array_can_be_sorted/test_solution.py):

```python theme={"theme":{"light":"github-light","dark":"github-dark"}}
class Solution:
    # Time: O(n^2) worst case from sorting each segment
    # Space: O(n) for the working copy
    def can_sort_array(self, nums: list[int]) -> bool:
        arr = list(nums)
        n = len(arr)
        i = 0
        while i < n:
            bits = arr[i].bit_count()
            j = i
            while j < n and arr[j].bit_count() == bits:
                j += 1
            arr[i:j] = sorted(arr[i:j])
            i = j
        return arr == sorted(nums)
```

## Complexity

| Time | Space |
| - | - |
| O(n^2) worst case from sorting each segment | O(n) for the working copy |

## Tags

[NeetCode All](/catalog/neetcode).


This documentation is built and hosted on [Mintlify](https://mintlify.com), a developer documentation platform.