Rearrange an array such that ‘arr[j]’ becomes ‘i’ if ‘arr[i]’ is ‘j’

Problem Statement

The problem ” Rearrange an array such that ‘arr[j]’ becomes ‘i’ if ‘arr[i]’ is ‘j’ ” states that you have an “n” sized array containing integers. The numbers in the array are in a range of 0 to n-1. The problem statement asks to rearrange the array in such a way that the array[i] = j becomes arr[ j ] = i.

Example

arr[]={1,3,5,2,0,4}

4 0 3 1 5 2

Explanation

arr[0]=1 is changed to arr[1]=0

arr[1]=3 is changed to arr[3]=1

arr[2]=5 is changed to arr[5]=2

arr[3]=2 is changed to arr[2]=3

arr[4]=0 is changed to arr[0]=4

arr[5]=4 is changed to arr[4]=5

so when printed ⇒

arr[0] ⇒ arr[1] ⇒ arr[2] ⇒ arr[3] ⇒ arr[4] ⇒ arr[5]

⇒ 4 0 3 1 5 2

Algorithm to Rearrange an array such that ‘arr[j]’ becomes ‘i’ if ‘arr[i]’ is ‘j’

1. Traverse the array from 0 to n-1(inclusively).
    1. Do arr [ arr % n ] + = i * n.
2. Then update the value of arr[ i ] =arr[ i ] / n.
3. Print the array.

Explanation

Given an array of integers. The numbers it holds is within the range of 0 to n – 1. We will rearrange the numbers pf array. So that the elements in the array becomes such that arr[j] = i if it is arr[i] = j. Thus this means if we have some value at the ith position as j, then change that value to the jth position of an array. Also, we have given array elements within the range 0 to n-1. So the number cannot exceed the length of an array. So it can be beneficial when we traverse the array, we can take any number value as an index and perform some operations on it.

Because we are going to perform some operations on the array itself. We will pick each array element and find the modulo of arr[i]%n, where n is the length of an array. Now, as we mentioned earlier that the numbers are in the range of 0 to n-1.  So when we find out the modulo of any number with the n. It will not exceed the number greater than an index of the array, because the modulo of arr[i]%n will be treated as an index of array again. And then we store it in the multiplication of i*n. Update each value of modulo as an index of the array and sum it with itself.

We are just doing this to store and update the values in the array if we going to fetch them. We just have to divide them. Because if you multiply the number with x and divide with the x the number will become neutral as it is. Update the arr[i] by dividing the same arr[i] by n and store it to arr[i]. In this way, we will get the desired result. That is how to rearrange an array such that ‘arr[j]’ becomes ‘i’ if ‘arr[i]’ is ‘j’.

Code

C++ code to Rearrange an array such that ‘arr[j]’ becomes ‘i’ if ‘arr[i]’ is ‘j’

#include<iostream>

using namespace std;

void rearrangeIndexValue(int arr[], int n)
{
    for (int i = 0; i < n; i++)
    {
        arr[arr[i] % n] += i * n;
    }

    for (int i = 0; i < n; i++)
    {
        arr[i] /= n;
    }
}
void printArray(int arr[], int n)
{
    for (int i = 0; i < n; i++)
        cout << arr[i] << " ";
}
int main()
{
    int arr[] = { 1,3,5,2,0,4};
    int n = sizeof(arr) / sizeof(arr[0]);

    cout << "Array after modifying :";
    rearrangeIndexValue(arr,n);
    printArray(arr, n);

    return 0;
}

Array after modifying :4 0 3 1 5 2

Java code to Rearrange an array such that ‘arr[j]’ becomes ‘i’ if ‘arr[i]’ is ‘j’

class rearrangeArray2
{
    public static void rearrangeIndexValue(int arr[], int n)
    {
        for (int i = 0; i < n; i++)
        {
            arr[arr[i] % n] += i * n;
        }
        for (int i = 0; i < n; i++)
        {
            arr[i] /= n;
        }
    }
    public static void printArray(int arr[], int n)
    {
        for (int i = 0; i < n; i++)
        {
            System.out.print(arr[i] + " ");
        }
        System.out.println();
    }
    public static void main(String[] args)
    {
        int arr[] = { 1,3,5,2,0,4};
        int n = arr.length;

        rearrangeIndexValue(arr, n);

        System.out.print("Array after modifying : ");
        printArray(arr, n);
    }
}

Array after modifying : 4 0 3 1 5 2

Complexity Analysis

Time Complexity

O(n) where “n” is the number of elements in the array. Even though we traversed over the elements of array twice. So, this still counts as linear time complexity only.

Space Complexity

O(n) where “n” is the number of elements in the array. Since we have not stored anything related to each element and have been taking only constant space. So, space complexity for the algorithm is constant.