Rearrange an array with O(1) extra space

PROBLEM :

Given an array arr[] of size n where every element is in range from 0 to n-1. Rearrange the given array so that arr[i] becomes arr[arr[i]]. This should be done with O(1) extra space.


Input:

First line contains an integer denoting the test cases 'T'. Every test case contains an integer value depicting size of array 'N' and N integer elements are to be inserted in the next line with spaces between them.


Output:

Print all elements of the array after rearranging, each separated by a space, in separate line for each test case.


Constraints:

1 <= T <= 70
1 <= N<= 100
1 <= Arr[i] <= 100
Arr[i]<=N


Example:

Input:

3
2
1 0
5
4 0 2 1 3
4
3 2 0 1

Output:

0 1
3 4 2 0 1
1 0 3 2

--------------------------------------------------------------------------------
SIMPLE c++ IMPLEMENTATION :(Using Auxilary arry)
--------------------------------------------------------------------------------

#include<iostream>
using namespace std;
void Rearrange_an_array(int [],int ) ;
int main()
 {
int t,no,arr[100],i ;
cin>>t ;
while(t--)
{
   cin>>no ;
   for(i=0;i<no;i++)
       cin>>arr[i] ;
     
   Rearrange_an_array(arr,no) ;
 
   for(i=0;i<no;i++)
       cout<<arr[i]<<" " ;
   cout<<endl ;
}
return 0;
}

void Rearrange_an_array(int arr[],int no)
{
    int i ;
    int temp[no] ;
   
    for(i=0;i<no;i++)
        temp[i]=arr[arr[i]] ;
       
    for(i=0;i<no;i++)
        arr[i]=temp[i] ;
}

--------------------------------------------------------------------------------
SIMPLE c++ IMPLEMENTATION :(Using O(1) space)
--------------------------------------------------------------------------------

#include<iostream>
using namespace std;
void Rearrange_an_array(int [],int ) ;
int main()
 {
int t,no,arr[100],i ;
cin>>t ;
while(t--)
{
   cin>>no ;
   for(i=0;i<no;i++)
       cin>>arr[i] ;
     
   Rearrange_an_array(arr,no) ;
 
   for(i=0;i<no;i++)
       cout<<arr[i]<<" " ;
   cout<<endl ;
}
return 0;
}

void Rearrange_an_array(int arr[],int no)
{
    int i ;
   
    for(i=0;i<no;i++)
        arr[i]=arr[i]+(arr[arr[i]]%no)*no ;
       
    for(i=0;i<no;i++)
        arr[i]=arr[i]/no ;
   
}

---------------------------------------------------------------------------------