Rearrange an array so that arr becomes arr] and only use O(1) extra space, implemented in C++

We get an array of positive integer type, say, arr[] of any given size, such that the element value in the array should be greater than 0 but less than the size of the array. The task is to rearrange An array that only turns arr[i] into arr[arr[i]] in the given O(1) space and prints the final result.

Let’s look at various input and output scenarios for this situation −

Input− int arr[] = {0 3 2 1 5 4 }

Output− Array before sorting: 0 3 2 1 5 4 Rearrange the array so that arr[i] becomes arr[arr[i]], with O(1) extra space: 0 1 2 3 4 5

Explanation− We give Define an integer array of size 6, and all elements in the array have values ​​less than 6. Now, we will rearrange the array so that arr[arr[0] is 0, arr[arr[1]] is 1, arr[arr [2]] is 2, arr[arr[3]] is 3, arr[ arr[4]] is 4, arr[arr[5]] is 5. Therefore, the final array after rearrangement is 0 1 2 3 4 5.

input− int arr[] = {1, 0}

output − Array before sorting: 1 0 Rearrange the array so that arr[i] becomes arr[arr[i]], where O(1) extra space is: 0 1

Explanation - We get an integer of size 2 An array where all elements in the array have values ​​less than 2. Now, we will rearrange the array so that arr[arr[0] is 1 and arr[arr[1]] is 0. Therefore, the final array after rearrangement is 0 1.

Input− int arr[] = {1, 0, 2, 3}

Output−Array before sorting: 1 0 2 3 Rearrange the array so that arr[i] becomes arr[arr[i]], with O(1) extra space: 0 1 2 3

Explanation - We give the size is an integer array of 4, and all elements in the array have values ​​less than 4. Now, we will rearrange the array so that arr[arr[0] is 0, arr[arr[1]] is 1, arr[arr[2] ]] is 2, and arr[arr[3]] is 3. Therefore, the final array after rearrangement is 0 1 2 3.

The method used in the following program is as follows

• Input an array of integer elements and calculate the array size

• Before printing array, call the function Rearrangement (arr, size)

• Function internal rearrangement (arr, size)

  • Start loop FOR from i to 0 until i is less than size. Inside the loop, set temp to arr[arr[i]] % size and arr[i] = temp * size.

  • Start looping FOR from i to 0 until i is less than size. Within the loop, set arr[i] = arr[i] / size

• to print the result.

Example

#include <bits/stdc++.h>
using namespace std;
void Rearrangement(int arr[], int size){
   for(int i=0; i < size; i++){
      int temp = arr[arr[i]] % size;
      arr[i] += temp * size;
   }
   for(int i = 0; i < size; i++){
      arr[i] = arr[i] / size;
   }
}
int main(){
   //input an array
   int arr[] = {0, 3, 2, 1, 5, 4};
   int size = sizeof(arr) / sizeof(arr[0]);
   //print the original Array
   cout<<"Array before Arrangement: ";
   for (int i = 0; i < size; i++){
      cout << arr[i] << " ";
   }
   //calling the function to rearrange the array
   Rearrangement(arr, size);
   //print the array after rearranging the values
   cout<<"\nRearrangement of an array so that arr[i] becomes arr[arr[i]] with O(1) extra space is: ";
   for(int i = 0; i < size; i++){
      cout<< arr[i] << " ";
   }
   return 0;
}

Output

If we run the above code it will generate the following output

Array before Arrangement: 0 3 2 1 5 4
Rearrangement of an array so that arr[i] becomes arr[arr[i]] with O(1) extra space is: 0 1 2 3 4 5

The above is the detailed content of Rearrange an array so that arr becomes arr] and only use O(1) extra space, implemented in C++. For more information, please follow other related articles on the PHP Chinese website!