Fill the missing numbers in the array of N natural numbers such that arr [ i ] not equal to i | C ++ 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
#include <bits/stdc++.h> NEW_LINE using namespace std ; void printArray ( int [ ] , int ) ; void solve ( int arr [ ] , int n ) { set < int > unfilled_indices ; set < int > missing ; for ( int i = 1 ; i < n ; i ++ ) missing . insert ( i ) ; for ( int i = 1 ; i < n ; i ++ ) { if ( arr [ i ] == 0 ) unfilled_indices . insert ( i ) ; else { auto it = missing . find ( arr [ i ] ) ; missing . erase ( it ) ; } } auto it2 = missing . end ( ) ; it2 -- ; for ( auto it = unfilled_indices . begin ( ) ; it != unfilled_indices . end ( ) ; it ++ , it2 -- ) { arr [ * it ] = * it2 ; } 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 . find ( i ) != unfilled_indices . end ( ) ) { x = arr [ i ] ; arr [ i ] = pos ; arr [ pos ] = x ; break ; } } } } printArray ( arr , n ) ; } void printArray ( int arr [ ] , int n ) { for ( int i = 1 ; i < n ; i ++ ) cout << arr [ i ] << " ▁ " ; } int main ( ) { int arr [ ] = { 0 , 7 , 4 , 0 , 3 , 0 , 5 , 1 } ; int n = sizeof ( arr ) / sizeof ( arr [ 0 ] ) ; solve ( arr , n ) ; return 0 ; }