- Iterate through elements in an array
- If arr[i] >= 0 && arr[i] != i, put arr[i] at i ( swap arr[i] with arr[arr[i]])
Below is the implementation of above approach.
- C++
// C++ program for rearrange an
// array such that arr[i] = i.
#include <stdio.h>
void fixArray( int arr[], int n)
{
`` for ( int i = 0; i < n;)
`` {
`` if (arr[i] >= 0 && arr[i] != i)
`` arr[arr[i]] = (arr[arr[i]] + arr[i])
`` - (arr[i] = arr[arr[i]]);
`` else
`` i++;
`` }
}
// Driver Code
int main()
{
`` int arr[] = { -1, -1, 6, 1, 9, 3, 2, -1, 4, -1 };
`` int n = sizeof (arr) / sizeof (arr[0]);
`` // Fucnction Call
`` fixArray(arr, n);
`` // Print output
`` for ( int i = 0; i < n; i++)
`` printf ( "%d " , arr[i]);
`` return 0;
}
Output
-1 1 2 3 4 -1 6 -1 -1 9
Time Complexity: O(n)
- JAVA
// Java program for rearrange an
// array such that arr[i] = i.
import java.util.Arrays;
class Program
{
public static void main(String[] args)
{
int [] arr = { - 1 , - 1 , 6 , 1 , 9 , 3 , 2 , - 1 , 4 , - 1 };
for ( int i = 0 ; i < arr.length;)
{
if (arr[i] >= 0 && arr[i] != i)
{
int ele = arr[arr[i]];
arr[arr[i]] = arr[i];
arr[i] = ele;
}
else
{
i++;
}
}
System.out.println(Arrays.toString(arr));
}
}
Output
-1 1 2 3 4 -1 6 -1 -1 9
Time Complexity: O(n)