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]]. This should be done with O(1) extra space
Examples:
Input: arr[] = {3, 2, 0, 1}
Output: arr[] = {1, 0, 3, 2}
Explanation:
In the given array
arr[arr[0]] is 1 so arr[0] in output array is 1
arr[arr[1]] is 0 so arr[1] in output array is 0
arr[arr[2]] is 3 so arr[2] in output array is 3
arr[arr[3]] is 2 so arr[3] in output array is 2Input: arr[] = {4, 0, 2, 1, 3}
Output: arr[] = {3, 4, 2, 0, 1}
Explanation:
arr[arr[0]] is 3 so arr[0] in output array is 3
arr[arr[1]] is 4 so arr[1] in output array is 4
arr[arr[2]] is 2 so arr[2] in output array is 2
arr[arr[3]] is 0 so arr[3] in output array is 0
arr[arr[4]] is 1 so arr[4] in output array is 1Input: arr[] = {0, 1, 2, 3}
Output: arr[] = {0, 1, 2, 3}
Explanation:
arr[arr[0]] is 0 so arr[0] in output array is 0
arr[arr[1]] is 1 so arr[1] in output array is 1
arr[arr[2]] is 2 so arr[2] in output array is 2
arr[arr[3]] is 3 so arr[3] in output array is 3
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.
The array elements of the given array lie from 0 to n-1. Now an array element is needed that can store two different values at the same time. To achieve this, every element at ith index is incremented by (arr[arr[i]] % n)*n. After the increment operation of the first step, every element holds both old values and new values. An old value can be obtained by arr[i]%n and a new value can be obtained by arr[i]/n.
Follow the steps below the solve the given problem:
- Traverse the array from start to end.
- 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.
- Again Traverse the array from start to end
- Print the ith element after dividing the ith element by n, i.e. array[i]/n.
Below is the implementation of the above approach:
C++
#include <iostream>using namespace std;// The function to rearrange an array// in-place so that arr[i] becomes arr[arr[i]].void rearrange(int arr[], int n){ // First step: Increase all values by (arr[arr[i]]%n)*n for (int i = 0; i < n; i++) arr[i] += (arr[arr[i]] % n) * n; // Second Step: Divide all values by n for (int i = 0; i < n; i++) arr[i] /= n;}// A utility function to print an array of size nvoid printArr(int arr[], int n){ for (int i = 0; i < n; i++) cout << arr[i] << " "; cout << endl;}/* Driver program to test above functions*/int main(){ int arr[] = { 3, 2, 0, 1 }; int n = sizeof(arr) / sizeof(arr[0]); cout << "Given array is \n"; printArr(arr, n); rearrange(arr, n); cout << "Modified array is \n"; printArr(arr, n); return 0;} |
Java
class Rearrange { // The function to rearrange an array in-place so that // arr[i] becomes arr[arr[i]]. void rearrange(int arr[], int n) { // First step: Increase all values by // (arr[arr[i]]%n)*n for (int i = 0; i < n; i++) arr[i] += (arr[arr[i]] % n) * n; // Second Step: Divide all values by n for (int i = 0; i < n; i++) arr[i] /= n; } // A utility function to print an array of size n void printArr(int arr[], int n) { for (int i = 0; i < n; i++) System.out.print(arr[i] + " "); System.out.println(""); } /* Driver program to test above functions */ public static void main(String[] args) { Rearrange rearrange = new Rearrange(); int arr[] = { 3, 2, 0, 1 }; int n = arr.length; System.out.println("Given Array is :"); rearrange.printArr(arr, n); rearrange.rearrange(arr, n); System.out.println("Modified Array is :"); rearrange.printArr(arr, n); }}// This code has been contributed by Mayank Jaiswal |
Python3
# Python3 program to Rearrange# an array so that arr[i] becomes# arr[arr[i]]# The function to rearrange an# array in-place so that arr[i]# becomes arr[arr[i]].def rearrange(arr, n): # First step: Increase all values # by (arr[arr[i]] % n) * n for i in range(0, n): arr[i] += (arr[arr[i]] % n) * n # Second Step: Divide all values # by n for i in range(0, n): arr[i] = int(arr[i] / n)# A utility function to print# an array of size ndef printArr(arr, n): for i in range(0, n): print(arr[i], end=" ") print("")# Driver programarr = [3, 2, 0, 1]n = len(arr)print("Given array is")printArr(arr, n)rearrange(arr, n)print("Modified array is")printArr(arr, n)# This code is contributed by shreyanshi_arun |
C#
// C# Program to rearrange an array// so that arr[i] becomes arr[arr[i]]// with O(1) extra spaceusing System;class Rearrange { // Function to rearrange an // array in-place so that arr[i] // becomes arr[arr[i]]. void rearrange(int[] arr, int n) { // First step: Increase all values // by (arr[arr[i]] % n) * n for (int i = 0; i < n; i++) arr[i] += (arr[arr[i]] % n) * n; // Second Step: Divide all values by n for (int i = 0; i < n; i++) arr[i] /= n; } // A utility function to // print an array of size n void printArr(int[] arr, int n) { for (int i = 0; i < n; i++) Console.Write(arr[i] + " "); Console.WriteLine(""); } // Driver Code public static void Main() { Rearrange rearrange = new Rearrange(); int[] arr = { 3, 2, 0, 1 }; int n = arr.Length; Console.Write("Given Array is :"); rearrange.printArr(arr, n); rearrange.rearrange(arr, n); Console.Write("Modified Array is :"); rearrange.printArr(arr, n); }}// This code has been contributed by Nitin Mittal. |
PHP
<?php // The function to rearrange an array // in-place so that arr[i] becomes arr[arr[i]].function rearrange(&$arr, $n){ // First step: Increase all values // by (arr[arr[i]]%n)*n for ($i = 0; $i < $n; $i++) $arr[$i] += ($arr[$arr[$i]] % $n) * $n; // Second Step: Divide all values by n for ($i = 0; $i < $n; $i++) $arr[$i] = intval($arr[$i] / $n);}// A utility function to print // an array of size nfunction printArr(&$arr, $n){ for ($i = 0; $i < $n; $i++) echo $arr[$i] ." "; echo "\n";}// Driver Code$arr = array(3, 2, 0, 1);$n = sizeof($arr);echo "Given array is \n";printArr($arr, $n);rearrange($arr, $n);echo "Modified array is \n";printArr($arr, $n);// This code is contributed // by ChitraNayal?> |
Javascript
<script>// The function to rearrange an array // in-place so that arr[i] becomes arr[arr[i]].function rearrange(arr, n){ // First step: Increase all values by (arr[arr[i]]%n)*n for (let i = 0; i < n; i++) arr[i] += (arr[arr[i]] % n) * n; // Second Step: Divide all values by n for (let i = 0; i < n; i++) arr[i] = Math.floor(arr[i] / n);}// A utility function to print an array of size nfunction printArr(arr, n){ for (let i = 0; i < n; i++) document.write(arr[i] + " "); document.write("<br>");}/* Driver program to test above functions*/ let arr = [3, 2, 0, 1]; let n = arr.length; document.write("Given array is <br>"); printArr(arr, n); rearrange(arr, n); document.write("Modified array is <br>"); printArr(arr, n);// This code is contributed by Surbhi Tyagi.</script> |
Given array is 3 2 0 1 Modified array is 1 0 3 2
Time Complexity: O(N), Only two traversal of the array is needed. So time complexity is O(N).
Auxiliary Space: O(1), No extra space is required.
Note: The problem with the above solution is, that it may cause an overflow.
The credit for this solution goes to Ganesh Ram Sundaram.
Here is a better solution:
Rearrange an array such that ‘arr[j]’ becomes ‘i’ if ‘arr[i]’ is ‘j’
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
