> For the complete documentation index, see [llms.txt](https://mayanktyagi3111.gitbook.io/interview-prep/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://mayanktyagi3111.gitbook.io/interview-prep/maths/rearrange-array.md).

# Rearrange Array

Rearrange a given array so that `Arr[i]` becomes `Arr[Arr[i]]` with `O(1)` extra space.

**Example:**

```
Input : [1, 0]
Return : [0, 1]
```

> Lets say `N` = `size of the array`. Then, following holds true :
>
> * **All elements in the array are in the range `[0, N-1]`**
> * **`N * N` does not overflow for a signed integer**

```java
public class Solution {
    public void arrange(ArrayList<Integer> arr) {
        int n = arr.size();
        for (int i = 0; i < n; i++)
            arr.set(i, arr.get(i) + (arr.get(arr.get(i)) % n) * n);
        for (int i = 0; i < n; i++)
            arr.set(i, arr.get(i) / n);
    }
}
```