Rearrange an array with O(1) extra space


Tue Feb 08 2022 05:08:33 GMT+0000 (Coordinated Universal Time)

Saved by @Uttam #java #gfg #geeksforgeeks #arrays #practice #rearrange

class Solution
    //Function to rearrange an array so that arr[i] becomes arr[arr[i]]
    //with O(1) extra space. 
    static void arrange(long arr[], int n)
        int i = 0;
        //Increasing all values by (arr[arr[i]]%n)*n to store the new element.
        for(i = 0; i < n; i++)
        //Since we had multiplied each element with n.
        //We will divide by n too to get the new element at that 
        //position after rearranging.
        for(i = 0; i < n; i++)
            arr[(int)i] = arr[(int)i]/n;

Rearrange an array with O(1) extra space Given an array arr[] of size N where every element is in the range from 0 to n-1. Rearrange the given array so that arr[i] becomes arr[arr[i]]. Example 1: Input: N = 2 arr[] = {1,0} Output: 0 1 Explanation: arr[arr[0]] = arr[1] = 0. arr[arr[1]] = arr[0] = 1. Example 2: Input: N = 5 arr[] = {4,0,2,1,3} Output: 3 4 2 0 1 Explanation: arr[arr[0]] = arr[4] = 3. arr[arr[1]] = arr[0] = 4. and so on. Your Task: You don't need to read input or print anything. The task is to complete the function arrange() which takes arr and N as input parameters and rearranges the elements in the array in-place. Expected Time Complexity: O(N) Expected Auxiliary Space: O(1) Constraints: 1 <= N <= 10^7 0 <= Arr[i] < N --------------------------------------------------------------------------------------------------------- Approach: The array elements of the given array lies from 0 to n-1. Now an array element is needed that can store two different values at the same time. To achieve this increment every element at ith index is incremented by (arr[arr[i]] % n)*n.After the increment operation of first step, every element holds both old values and new values. Old value can be obtained by arr[i]%n and a new value can be obtained by arr[i]/n. How this can be achieved? Let's assume an element is a and another element is b, both the elements are less than n. So if an element a is incremented by b*n. So the element becomes a + b*n so when a + b*n is divided by n then the value is b and a + b*n % n is a. Algorithm: ------------ 1.) Traverse the array from start to end. 2.) For every index increment the element by array[array[index] ] % n. To get the ith element find the modulo with n, i.e array[index]%n. 3.) Again Travsese the array from start to end 4.) Print the ith element after dividing the ith element by n, i.e. array[i]/n.