Given an array of elements of length N, ranging from 0 to N – 1. All elements may not be present in the array. If element is not present then there will be -1 present in the array. Rearrange the array such that A[i] = i and if i is not present, display -1 at that place.

Examples:

Input : arr = {-1, -1, 6, 1, 9, 3, 2, -1, 4, -1}
Output : [-1, 1, 2, 3, 4, -1, 6, -1, -1, 9]

Input : arr = {19, 7, 0, 3, 18, 15, 12, 6, 1, 8,
              11, 10, 9, 5, 13, 16, 2, 14, 17, 4}
Output : [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 
         11, 12, 13, 14, 15, 16, 17, 18, 19]

METHOD 1

import java.lang.reflect.Array;
import java.util.Arrays;

/**
 * Question   : Rearrange an array such that arr[i] = i
 * Complexity : Time: O(n) ; Space: O(1)
 * Time       : 2020/06/11
 * Author     : Max
 */
public class RearrangeAnArray {
    public static void rearrange(int[] arr) {
        if (arr == null || arr.length == 0) {
            return;
        }

        int n = arr.length;

        for (int i = 0; i < n; i++) {
            int number = arr[i] % n;
            if (number >= 0) {
                if (arr[number] < 0) {
                    arr[number] -= n;
                } else {
                    arr[number] += n;
                }
            }
        }

        for (int i = 0; i < n; i++) {
            arr[i] /= n;
        }

        for (int i = 0; i < n; i++) {
            if (arr[i] == 1 || arr[i] == -1) {
                arr[i] = i;
            } else {
                arr[i] = -1;
            }
        }
    }

    public static void main(String[] args) {
        int[] arr = new int[]{0, 2, -1, 4, 1};
        rearrange(arr);
        System.out.println(Arrays.toString(arr));
    }
}