Another Approach:
- Navigate through the array.
- Check if a[i] = -1, if yes then ignore it.
- If a[i] != -1, Check if element a[i] is at its correct position (i=A[i]) . If yes then ignore it.
- If a[i] != -1 and element a[i] is not at its correct position (i!=A[i]) then place it to its correct position, but there are two conditions:
- Either A[i] is vacate , means A[i] = -1 , then just put A[i] = i .
- OR A[i] is not vacate , means A[i] = x , then int y=x put A[i] = i . Now, we need to place y to its correct place, so repeat from step 3.
Below is the implementation for the above approach:
- C++
// C++ program for rearrange an
// array such that arr[i] = i.
#include <bits/stdc++.h>
using namespace std;
// Function to rearrange an array
// such that arr[i] = i.
void fixArray( int A[], int len)
{
`` for ( int i = 0; i < len; i++)
`` {
`` if (A[i] != -1 && A[i] != i)
`` {
`` int x = A[i];
`` // check if desired place
`` // is not vacate
`` while (A[x] != -1 && A[x] != x)
`` {
`` // store the value from
`` // desired place
`` int y = A[x];
`` // place the x to its correct
`` // position
`` A[x] = x;
`` // now y will become x, now
`` // search the place for x
`` x = y;
`` }
`` // place the x to its correct
`` // position
`` A[x] = x;
`` // check if while loop hasn't
`` // set the correct value at A[i]
`` if (A[i] != i)
`` {
`` // if not then put -1 at
`` // the vacated place
`` A[i] = -1;
`` }
`` }
`` }
}
// Driver code
int main()
{
`` int A[] = { -1, -1, 6, 1, 9,
`` 3, 2, -1, 4, -1 };
`` int len = sizeof (A) / sizeof (A[0]);
`` // Function Call
`` fixArray(A, len);
`` // Print the output
`` for ( int i = 0; i < len; i++)
`` cout << A[i] << " " ;
}
Output
-1 1 2 3 4 -1 6 -1 -1 9