5

Permutation transformation: Minimum operations to achieve permutation

 11 months ago
source link: https://www.geeksforgeeks.org/permutation-transformation-minimum-operations-to-achieve-permutation/
Go to the source link to view the article. You can view the picture content, updated content and better typesetting reading experience. If the link is broken, please click the button below to view the snapshot at that time.

Permutation transformation: Minimum operations to achieve permutation

Given an array arr[] of lengthn, the task is to find the minimum number of operations required to make a permutation of integers 1 to n where you are allowed to select any element arr[i] and replace it with arr[i] % x (x is any positive integer). If it is not possible to make a permutation return -1.

Examples:

Input: n = 5, arr[] = {2, 3, 4, 4, 5}
Output: 1
Explanation: One way to make the given array a permutation of integers 1 to 5 is to perform the following operations:

  • Select arr3 = 4 and replace it with arr3 % 3 = 1.

After these operations, the array becomes [2, 3, 4, 1, 5], which is a permutation of integers 1 to 5. Therefore, the minimum number of operations required is 1.

Approach: This can be solved with the following idea:

To make the given array a permutation of integers 1 to n, we need to ensure that all the elements in the range 1 to n are present exactly once in the array arr. We can achieve this by performing the operation on the elements in the array that are either greater than n or repeated. By performing the operation on any element arri, we can convert it to any positive number less than floor((arri-1)/2). Since the maximum value of ai% x for any arbitrary x can be floor ((arri-1)/2), we can use this fact to ensure that all the elements in the range 1 to n are present exactly once in the array arr.

Below are the steps involved:

  • First creates a set containing integers from 1 to n and a vector to store elements that are not part of the permutation.
  • It then iterates over the input array and removes the elements from the set if they are present, and adds them to the vector otherwise.
  • The vector is then sorted in descending order.
  • It then iterates over the elements in the vector, and for each element, it finds the largest integer s in the set and each integer in the vector say z such that (z-1)/2 < s.  The reason for this condition is that whenever we apply operation z%x where x is any positive integer the result will be always less than (z-1)/2. If such an integer exists, it removes it from the set. If not, it sets a flag and exits the loop.
  • Finally, it outputs the size of the vector if the flag is not set, or -1 otherwise.

Below is the implementation of the above approach:

// C++ code for the above approach:
#include <bits/stdc++.h>
using namespace std;
void checkPermutation(int n, int arr[])
{
// Set to store elements from 1 to n
set<int> st;
for (int i = 1; i <= n; i++) {
st.insert(i);
}
// vector stores all the elements
// which are not present in set or
// repeated finally set stores the
// element missing from the array
// in range 1 to n.
vector<int> v;
for (int i = 0; i < n; i++) {
// Element is not present
// in the set.
if (st.find(arr[i]) == st.end()) {
v.push_back(arr[i]);
}
else {
st.erase(arr[i]);
}
}
// Sorting element in decending order
// in vector v
sort(v.begin(), v.end());
reverse(v.begin(), v.end());
// If it is impossible to convert
// array in permutation of 1 to n
// flag will be true
bool flag = false;
for (auto z : v) {
auto it = st.end();
it--;
int s = *it;
if ((z - 1) / 2 < s) {
flag = true;
break;
}
st.erase(it);
}
if (flag) {
cout << "-1"
<< "\n";
}
else {
cout << v.size() << "\n";
}
}
// Driver code
int main()
{
int n = 5;
int arr[n] = { 2, 3, 4, 4, 5 };
// Function call
checkPermutation(n, arr);
return 0;
}
Output

Time complexity: O(n*logn)
Auxiliary Space: O(n)


report

Recommend

About Joyk


Aggregate valuable and interesting links.
Joyk means Joy of geeK