Given an array arr[] of size N, the task is to find the minimum number of operations required to make the array a permutation of numbers in range [1, N] where, in each operation, an element at any index i can be replaced by arr[i]%k (k = any value greater than 0). Return -1 if the array cannot be made a permutation of numbers in range [1, N].
Examples:
Input: arr [] = {1, 7}, N = 2
Output: 1
Explanation: The only possible sequence of operations which minimizes the no of operations is
Choose i = 1, k = 5. Perform arr[1] = arr[1] % 5 = 2.Input: arr [] = {1,5,4}, N = 3
Output: -1
Explanation: It is impossible to obtain a permutation of integers from 1 to N.
Approach: The problem can be solved on the basis of the following observation.
x % y < (x/2) if x ≥ y, and
x % y = x if x < y.As bigger is x, the longer the range of values that can be obtained after one mod operation.
So try to, assign smaller arr[i] to smaller numbers in the resulting permutation.Although, if arr[i] satisfies 1 ≤ arr[i] ≤ N, just leave it there and use it in the resulting permutation.
if multiple arr[i] satisfy the same condition and have the same value, just choose one.
Let’s suppose in the optimal solution, l is changed to m and n to l for some n > l > m (l, m, n are values, not indices).
Then keeping l intact and changing n to m uses 1 less operation.
And, if it is possible to change n to l, then it must be possible to change n to m.
Follow the steps mentioned below to implement the approach:
- Sort the array.
- If 1 ≤ arr[i] ≤ N and it is the first occurrence of the element with value arr[i], leave it there.
- Else, let the current least unassigned value in the resulting permutation be x:
- If x < arr[i]/2, assign the current element to value x and add the number of operations by 1.
- Else, output −1 directly.
Below is the implementation of the above approach.
C++
// C++ code to implement above approach#include <bits/stdc++.h>using namespace std;// Function to find minimum operations// used to make permutation of 1 to Nvoid minoperation(vector<int> arr, int N){ set<int> st; vector<int> rem; // Storing one instance of every element // from 1 to N for (int i = 1; i <= N; i++) { st.insert(i); } for (int i = 0; i < N; i++) { if (st.find(arr[i]) != st.end()) st.erase(arr[i]); else rem.push_back(arr[i]); } // Sorting in descending order sort(rem.begin(), rem.end()); reverse(rem.begin(), rem.end()); int pt = 0; bool flag = false; for (auto& x : rem) { auto it = st.end(); it--; int p = (*it); if (p > (x - 1) / 2) { flag = true; break; } st.erase(it); } if (flag) { // Not possible to make permutation. cout << "-1"; } else { // Minimum number of operation required. cout << rem.size(); }}// Driver codeint main(){ int N = 3; vector<int> arr = { 1, 5, 4 }; minoperation(arr, N); return 0;} |
Java
// Java code to implement above approachimport java.util.*;class GFG{ // Function to find minimum operations // used to make permutation of 1 to N static void minoperation(int[] arr, int N) { HashSet<Integer> st = new HashSet<Integer>(); Vector<Integer> rem = new Vector<Integer>(); // Storing one instance of every element // from 1 to N for (int i = 1; i <= N; i++) { st.add(i); } for (int i = 0; i < N; i++) { if (st.contains(arr[i])) st.remove(arr[i]); else rem.add(arr[i]); } // Sorting in descending order Collections.sort(rem,Collections.reverseOrder()); boolean flag = false; for (int x : rem) { int it = st.size(); it--; int p = new ArrayList<>(st).get(it); if (p > (x - 1) / 2) { flag = true; break; } st.remove(it); } if (flag) { // Not possible to make permutation. System.out.print("-1"); } else { // Minimum number of operation required. System.out.print(rem.size()); } } // Driver code public static void main(String[] args) { int N = 3; int[] arr = { 1, 5, 4 }; minoperation(arr, N); }}// This code is contributed by 29AjayKumar |
C#
// C# code to implement above approachusing System;using System.Collections.Generic;class GFG{ // Function to find minimum operations // used to make permutation of 1 to N static void minoperation(int[] arr, int N) { HashSet<int> st = new HashSet<int>(); List<int> rem = new List<int>(); // Storing one instance of every element // from 1 to N for (int i = 1; i <= N; i++) { st.Add(i); } for (int i = 0; i < N; i++) { if (st.Contains(arr[i])) st.Remove(arr[i]); else rem.Add(arr[i]); } // Sorting in descending order rem.Sort(); rem.Reverse(); bool flag = false; foreach (int x in rem) { int it = st.Count; it--; int p = new List<int>(st)[it]; if (p > (x - 1) / 2) { flag = true; break; } st.Remove(it); } if (flag) { // Not possible to make permutation. Console.Write("-1"); } else { // Minimum number of operation required. Console.Write(rem.Count); } } // Driver code public static void Main() { int N = 3; int[] arr = { 1, 5, 4 }; minoperation(arr, N); }}// This code is contributed by Saurabh jaiswal |
Python3
# Python 3 code to implement above approach# Function to find minimum operations# used to make permutation of 1 to Ndef minoperation(arr, N): st = set([]) rem = [] # Storing one instance of every element # from 1 to N for i in range(1, N + 1): st.add(i) for i in range(N): if (arr[i] in st): st.remove(arr[i]) else: rem.append(arr[i]) # Sorting in descending order rem.sort() rem.reverse() pt = 0 flag = False for x in rem: it = len(st) it -= 1 p = list(st)[it] if (p > (x - 1) / 2): flag = True break st.remove(it) if (flag): # Not possible to make permutation. print("-1") else: # Minimum number of operation required. print(len(rem))# Driver codeif __name__ == "__main__": N = 3 arr = [1, 5, 4] minoperation(arr, N) # This code is contributed by ukasp. |
Javascript
<script> // JavaScript code for the above approach // Function to find minimum operations // used to make permutation of 1 to N function minoperation(arr, N) { let st = new Set(); let rem = []; // Storing one instance of every element // from 1 to N for (let i = 1; i <= N; i++) { st.add(i); } for (let i = 0; i < N; i++) { if (st.has(arr[i])) st.delete(arr[i]); else rem.push(arr[i]); } // Sorting in descending order rem.sort(function (a, b) { return b - a }) rem.reverse(); let pt = 0; let flag = false; for (let x of rem) { let it = [...st].pop(); let p = (it); if (p > Math.floor((x - 1) / 2)) { flag = true; break; } st.delete(it); } if (flag) { // Not possible to make permutation. document.write(-1) } else { // Minimum number of operation required. document.write(rem.size) } } // Driver code let N = 3; let arr = [1, 5, 4]; minoperation(arr, N); // This code is contributed by Potta Lokesh </script> |
-1
Time Complexity: O(N * logN)
Auxiliary Space: O(N)
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
