- Store all the numbers present in the array into a HashSet
- Iterate through the length of the array, if the corresponding position element is present in the HashSet, then set A[i] = i, else A[i] = -1
Below is the implementation of the above approach.
- C++
#include <iostream>
#include <unordered_map>
using namespace std;
//
void fixArray( int arr[], int n)
{
`` // Initialize a hashmap
`` std::unordered_map< int , int > hmap;
``
`` // Enter each element in hmap
`` for ( int i{0}; i<n; i++)
`` {
`` if (arr[i] != -1)
`` hmap[arr[i]] = 1;
`` }
``
`` // Navigate through array,
`` // and put A[i] = i,
`` // if i is present in hmap
`` for ( int i{0}; i<n; i++)
`` {
`` // if i(index) is found in hmap
`` if (hmap.find(i) != hmap.end())
`` {
`` arr[i] = i;
`` }
`` // if i not found
`` else
`` {
`` arr[i] = -1;
`` }
`` }
``
}
// Driver Code
int main() {
``
`` // Array initialization
`` int arr[] {-1, -1, 6, 1, 9,
`` 3, 2, -1, 4,-1};
`` int n = sizeof (arr) / sizeof (arr[0]);
``
`` // Function Call
`` fixArray(arr, n);
``
`` // Print output
`` for ( int i{0}; i<n; i++)
`` std::cout << arr[i] << ' ' ;
``
`` return 0;
}
Output
-1 1 2 3 4 -1 6 -1 -1 9
- JAVA
// Java program for rearrange an
// array such that arr[i] = i.
import java.util.*;
import java.lang.*;
class GfG {
// Function to rearrange an array
// such that arr[i] = i.
public static int [] fix( int [] A)
{
Set<Integer> s = new HashSet<Integer>();
// Storing all the values in the HashSet
for ( int i = 0 ; i < A.length; i++)
{
s.add(A[i]);
}
for ( int i = 0 ; i < A.length; i++)
{
if (s.contains(i))
A[i] = i;
else
A[i] = - 1 ;
}
return A;
}
// Driver code
public static void main(String[] args)
{
int A[] = {- 1 , - 1 , 6 , 1 , 9 ,
3 , 2 , - 1 , 4 ,- 1 };
// Function calling
System.out.println(Arrays.toString(fix(A)));
}
}
Output
-1 1 2 3 4 -1 6 -1 -1 9