Fill the missing numbers in the array of N natural numbers such that arr [ i ] not equal to i | Java implementation of above approach ; Function to fill the position with arr [ i ] = 0 ; Inserting all elements in missing [ ] set from 1 to N ; Inserting unfilled positions ; Removing allocated_elements ; Loop for filling the positions with arr [ i ] != i ; Checking for any arr [ i ] = i ; Finding the suitable position in the array to swap with found i for which arr [ i ] = i ; Checking if the position is present in unfilled_position ; Swapping arr [ i ] & arr [ pos ] ( arr [ pos ] = pos ) ; Function to Print the array ; Driver Code
import java . io . * ; import java . util . * ; class GFG { static void solve ( int arr [ ] , int n ) { Set < Integer > unfilled_indices = new HashSet < Integer > ( ) ; Set < Integer > missing = new HashSet < Integer > ( ) ; for ( int i = 1 ; i < n ; i ++ ) { missing . add ( i ) ; } for ( int i = 1 ; i < n ; i ++ ) { if ( arr [ i ] == 0 ) { unfilled_indices . add ( i ) ; } else { missing . remove ( arr [ i ] ) ; } } int [ ] mi = new int [ missing . size ( ) ] ; int l = 0 ; for ( int x : missing ) { mi [ l ++ ] = x ; } int m = missing . size ( ) ; for ( int it : unfilled_indices ) { arr [ it ] = mi [ m - 1 ] ; m -- ; } int pos = 0 ; for ( int i = 1 ; i < n ; i ++ ) { if ( arr [ i ] == i ) { pos = i ; } } int x ; if ( pos != 0 ) { for ( int i = 1 ; i < n ; i ++ ) { if ( pos != i ) { if ( unfilled_indices . contains ( i ) ) { x = arr [ i ] ; arr [ i ] = pos ; arr [ pos ] = x ; break ; } } } } printArray ( arr , n ) ; } static void printArray ( int arr [ ] , int n ) { for ( int i = 1 ; i < n ; i ++ ) { System . out . print ( arr [ i ] + " ▁ " ) ; } } public static void main ( String [ ] args ) { int [ ] arr = { 0 , 7 , 4 , 0 , 3 , 0 , 5 , 1 } ; int n = arr . length ; solve ( arr , n ) ; } }