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