Rearrange Array

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

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

思路：

要想办法用一个数来encode两个数，很简单的方法就是把两个数concat起来，比如用2019代表20和19。
然后用2019/100来得到20，2019 % 100 来得到19.

Solution:

Time: O(n)
Space: O(1)

public class Solution {
    public void arrange(ArrayList<Integer> a) {
        int n = a.size();
        for (int i = 0; i < n; i ++) {
            int oldVal = a.get(i);
            int combinedVal = combined(oldVal, a.get(oldVal), n);
            a.set(i, combinedVal);
        }
        for (int i = 0; i < n; i ++) {
            a.set(i, getNewVal(a.get(i), n));
        }
    }
    
    private int combined(int old, int new, int n) {
        return old + (new % n) * n;
    }

    private int getNewVal(int combined, int n) {
        return combined / n;
    }
}