Program to Build an Array from Permutation.

Given an array arr[] having n number of elements with zero-based permutation, we need to build a result array of the same length where result[i] = arr[arr[i]] for each 0 <= i < arr.length and return result.

Note: A zero-based permutation array is an array of distinct integers from 0 to n -1 where n is the number of elements in the array. (alert-success)

Input: arr = [0, 2, 1, 5, 3, 4]

Output: result = [0, 1, 2, 4, 5, 3]

Explanation: 

result = [arr[arr[0]], arr[arr[1]], arr[arr[2]], arr[arr[3]], arr[arr[4]], arr[arr[5]]]

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

       = [0, 1, 2, 4, 5, 3]

Approach 1: Simply create a new array of the same size and store the values of arr[arr[i]] in the new array.

//C++ Program to Build an Array from Permutation.
#include<iostream>
#include<vector>
using namespace std;

vector<int> buildpermutation(vector<int> arr){
    //size of given array
    int n = arr.size();

    vector<int> result(n);

    for(int i = 0; i < n; i++){
        result[i] = arr[arr[i]];
    }

    return result;
}

int main(){
    vector<int> arr = {0, 2, 1, 5, 3, 4};

    vector<int> result = buildpermutation(arr);

    for(int i = 0; i < result.size(); i++){
        cout<<result[i]<<" ";
    }
}

Output:

0 1 2 4 5 3

Time Complexity: O(n)
Space Complexity: O(n)

Approach 2: The above solution is taking O(n) extra space. To solve this problem with O(1) space complexity, we need to find a way to store two values at one position. As we know that value of the input array ranges from 0 to n-1 where n is the number of elements present in the given array. To do this, we can store the input array value in modulo by n and get the required value by dividing the modified value by n. We can use the below formula to solve this problem.

[ arr[i] = arr[i] + n*(arr[arr[i]]%n) ]

Explanation: 

arr[0] = arr[0] + 6*(arr[arr[0]]%6)

         = 0 + 6*(arr[0]%6)

         = 0 + 6*(0%6)

         = 0 + 6*0

         = 0

arr[1] = arr[1] + 6*(arr[arr[1]]%6)

         = 2 + 6*(arr[2]%6)

         = 2 + 6*(1%6)

         = 2 + 6*1

         = 8

arr[2] = arr[2] + 6*(arr[arr[2]]%6)

         = 1 + 6*(arr[1]%6)

         = 1 + 6*(2%6)

         = 1 + 6*2

         = 13

arr[3] = arr[3] + 6*(arr[arr[3]]%6)

         = 5 + 6*(arr[5]%6)

         = 5 + 6*(4%6)

         = 5 + 6*4

         = 29

arr[4] = arr[4] + 6*(arr[arr[4]]%6)

         = 3 + 6*(arr[3]%6)

         = 3 + 6*(5%6)

         = 3 + 6*5

         = 33

arr[5] = arr[5] + 6*(arr[arr[5]]%6)

         = 4 + 6*(arr[4]%6)

         = 4 + 6*(3%6)

         = 4 + 6*3

         = 22

Now, all input array element is modified, and we can modulo the current value to get

input array elements or divide the current array elements with n to get the required

answer.

arr[0]/n = 0/6 =  0
arr[1]/n = 8/6 =  1
arr[2]/n = 13/6 = 2
arr[3]/n = 29/6 = 4
arr[4]/n = 33/6 = 5
arr[5]/n = 22/6 = 3

//C++ Program to Build an Array from Permutation.
#include<iostream>
#include<vector>
using namespace std;

vector<int> buildpermutation(vector<int> arr){
    //size of given array
    int n = arr.size();
    for(int i = 0; i <n; i++){
        arr[i] = arr[i] + n*(arr[arr[i]]%n);
    }
    for(int i = 0; i <n; i++){
        arr[i] = arr[i]/n;
    }
    return arr;
}

int main(){
    vector<int> arr = {0, 2, 1, 5, 3, 4};
    vector<int> result = buildpermutation(arr);
    for(int i = 0; i < result.size(); i++){
        cout<<result[i]<<" ";
    }
}

Output:

0 1 2 4 5 3

Time Complexity: O(n)
Space Complexity: (1)

👉Support Us by Sharing our post with others if you really found this useful and also share your valuable feedback in the comment section below so we can work on them and provide you best 😊.(alert-success)

Program to Build an Array from Permutation.

No comments:

Post a Comment