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]
Approach:
1. Navigate the array.
2. Check if a[i] = -1, if yes then ignore it.
3. If a[i] != -1, Check if element a[i] is at its correct position (i=A[i]). If yes then ignore it.
4. 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 above approach:
C++
// CPP 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. int fix( 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 function. int main() { int A[] = { -1, -1, 6, 1, 9, 3, 2, -1, 4, -1 }; int len = sizeof (A) / sizeof (A[0]); fix(A, len); for ( int i = 0; i < len; i++) cout << A[i] << " " ; } // This code is contributed by Smitha Dinesh Semwal |
Java
// Java program for rearrange an // array such that arr[i] = i. import java.util.*; import java.lang.*; public class GfG { // Function to rearrange an array // such that arr[i] = i. public static int [] fix( int [] A) { for ( int i = 0 ; i < A.length; 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 ; } } } return A; } // Driver function. public static void main(String[] args) { int A[] = {- 1 , - 1 , 6 , 1 , 9 , 3 , 2 , - 1 , 4 ,- 1 }; System.out.println(Arrays.toString(fix(A))); } } |
Python3
# Python3 program for rearrange an # array such that arr[i] = i. # Function to rearrange an array # such that arr[i] = i. def fix( A, len ): for i in range ( 0 , len ): if (A[i] ! = - 1 and A[i] ! = i): x = A[i]; # check if desired place # is not vacate while (A[x] ! = - 1 and A[x] ! = x): #store the value from # desired place 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 function. A = [ - 1 , - 1 , 6 , 1 , 9 , 3 , 2 , - 1 , 4 , - 1 ] fix(A, len (A)) for i in range ( 0 , len (A)): print (A[i],end = ' ' ) # This code is contributed by Saloni1297 |
C#
// C# program for rearrange // an array such that // arr[i] = i. using System; class GfG { // Function to rearrange an // array such that arr[i] = i. public static int [] fix( int [] A) { for ( int i = 0; i < A.Length; 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; } } } return A; } // Driver Code static void Main() { int []A = new int []{-1, -1, 6, 1, 9, 3, 2, -1, 4,-1}; Console.WriteLine( string .Join( "," , fix(A))); } } // This code is contributed by // Manish Shaw(manishshaw1) |
PHP
<?php // PHP program for rearrange an // array such that arr[i] = i. // Function to rearrange an // array such that arr[i] = i. function fix(& $A , $len ) { for ( $i = 0; $i < $len ; $i ++) { if ( $A [ $i ] != -1 && $A [ $i ] != $i ) { $x = $A [ $i ]; // check if desired // place is not vacate while ( $A [ $x ] != -1 && $A [ $x ] != $x ) { // store the value // from desired place $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 $A = array (-1, -1, 6, 1, 9, 3, 2, -1, 4, -1); $len = count ( $A ); fix( $A , $len ); for ( $i = 0; $i < $len ; $i ++) echo ( $A [ $i ]. " " ); // This code is contributed by // Manish Shaw(manishshaw1) ?> |
Output:
[-1, 1, 2, 3, 4, -1, 6, -1, -1, 9]
Another Approach (Using HashSet) :
1) Store all the numbers present in the array into a HashSet
2) 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 above approach.
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 function. 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))); } } |
Python3
# Python3program for rearrange an # array such that arr[i] = i. # Function to rearrange an array # such that arr[i] = i. def fix(A): s = set () # Storing all the values in the Set for i in range ( len (A)): s.add(A[i]) for i in range ( len (A)): # check for item if present in set if i in s: A[i] = i else : A[i] = - 1 return A # Driver code if __name__ = = "__main__" : A = [ - 1 , - 1 , 6 , 1 , 9 , 3 , 2 , - 1 , 4 , - 1 ] print (fix(A)) |
C#
// C# program for rearrange an // array such that arr[i] = i. using System; class GfG { // Function to rearrange // an array such that // arr[i] = i. static int [] fix( int []A) { for ( int i = 0; i < A.Length; 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; } } } return A; } // Driver Code static void Main() { int []A = new int []{-1, -1, 6, 1, 9, 3, 2, -1, 4,-1}; Console.Write( string .Join( "," , fix(A))); } } // This code is contributed by // Manish Shaw(manishshaw1) |
Output :
[-1, 1, 2, 3, 4, -1, 6, -1, -1, 9]
Another Approach (Swap elements in Array) :
1) Iterate through elements in array
2) 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> int main() { int arr[] = {-1, -1, 6, 1, 9, 3, 2, -1, 4, -1}; int n = sizeof (arr)/ sizeof (arr[0]); 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++; } for ( int i = 0; i < n; i++) printf ( "%d " ,arr[i]); return 0; } // This Code is Contributed by Adarsh_Verma |
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)); } } /* This Java code is contributed by PrinciRaj1992*/ |
C#
// C# program for rearrange an // array such that arr[i] = i. using System; namespace GFG { class Program { 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++; } } Console.WriteLine(String.Join( "," , arr)); } } } // This code is contributed by // Venkata VardhiReddy(venkata) |
Output :
[-1, 1, 2, 3, 4, -1, 6, -1, -1, 9]
Time Complexity: O(n)
leave a comment
0 Comments