Rearrange an array so that arr [ i ] becomes arr [ arr [ i ] ] with O ( 1 ) extra space |  ; The function to rearrange an array in - place so that arr [ i ] becomes arr [ arr [ i ] ] . ; First step : Increase all values by ( arr [ arr [ i ] ] % n ) * n ; Second Step : Divide all values by n ; A utility function to print an array of size n ; Driver program to test above functions
#include <iostream> NEW_LINE using namespace std ; void rearrange ( int arr [ ] , int n ) { for ( int i = 0 ; i < n ; i ++ ) arr [ i ] += ( arr [ arr [ i ] ] % n ) * n ; for ( int i = 0 ; i < n ; i ++ ) arr [ i ] /= n ; } void printArr ( int arr [ ] , int n ) { for ( int i = 0 ; i < n ; i ++ ) cout << arr [ i ] << " ▁ " ; cout << endl ; } int main ( ) { int arr [ ] = { 3 , 2 , 0 , 1 } ; int n = sizeof ( arr ) / sizeof ( arr [ 0 ] ) ; cout << " Given ▁ array ▁ is ▁ STRNEWLINE " ; printArr ( arr , n ) ; rearrange ( arr , n ) ; cout << " Modified ▁ array ▁ is ▁ STRNEWLINE " ; printArr ( arr , n ) ; return 0 ; }