Given an array arr of n integers. You want to make this array a permutation of integers 1 to n. In one operation you can choose two integers i (0 ≤ i < n) and x (x > 0), then replace arr[i] with arr[i] mod x, the task is to determine the minimum number of operations to achieve this goal otherwise return -1.
Note: A permutation is an array consisting of n distinct integers from 1 to n in arbitrary order.
Examples:
Input: n = 2, arr = {1, 7}
Output:1
Explanation: In the first operation, you will choose i = 1, and x = 5, so the arr[1] will be (7%5) = 2, now the array {1, 2} is a permutation.Input: n = 3, arr = {1, 5, 4}
Output: -1
Explanation: It’s not possible to make the 3rd element 2, or 3, so the answer will be -1.
Approach: This problem can be solved using Greedy Algorithm and Modulo Arithmetic.
The idea is to use the concept that any number x can be converted to y if y=x%m then y lies between 0 and ceil(x/2)-1. Thus, in the array, we just need to convert those numbers that are greater than n and those numbers that are less than or equal to n but are duplicates. Now just greedily pick a smaller number for conversion to a smaller element.
Steps that were to follow the above approach:
- Create a vis array to mark those permutations which have been found in the array or have been made by using the given operation.
- Sort the array to greedily pick smaller elements for conversion to smaller elements.
- Create an array v to store the maximum possible number that can be made from numbers > n and duplicates of numbers ≤ n
- Make a variable j to iterate from 1 to n and check if we have made this permutation.
- Iterate through vector v and initially iterate j to the permutation not found so far:
- If (v[i] ≥ permutation not found) then this permutation can be made and keep iterating forward.
- Otherwise making the permutation is not possible.
Below is the code to implement the above steps:
C++
// C++ code to implement the above approach#include <bits/stdc++.h>using namespace std;// Function to make permutationint makePermutation(int n, vector<int>& arr){ vector<int> vis(n + 1); sort(arr.begin(), arr.end()); vector<int> v; for (int i = 1; i <= n; i++) { if (arr[i - 1] <= n) { if (vis[arr[i - 1]]) v.push_back(arr[i - 1] & 1 ? arr[i - 1] / 2 : arr[i - 1] / 2 - 1); vis[arr[i - 1]] = 1; } else v.push_back(arr[i - 1] & 1 ? arr[i - 1] / 2 : arr[i - 1] / 2 - 1); } int j = 1; int ans = 0; for (int i = 0; i < v.size(); i++) { while (vis[j]) j++; if (v[i] >= j) j++; else return -1; ans++; } return ans;}// Driver's codeint main(){ // Input array vector<int> arr = { 1, 7 }; // Function call cout << makePermutation(2, arr) << endl; return 0;} |
Java
// Java code to implement the above approachimport java.util.*;public class Main { // Function to make permutation public static int makePermutation(int n, List<Integer> arr) { List<Integer> vis = new ArrayList<>( Collections.nCopies(n + 1, 0)); Collections.sort(arr); List<Integer> v = new ArrayList<>(); for (int i = 1; i <= n; i++) { if (arr.get(i - 1) <= n) { if (vis.get(arr.get(i - 1)) != 0) v.add((arr.get(i - 1) & 1) == 1 ? arr.get(i - 1) / 2 : arr.get(i - 1) / 2 - 1); vis.set(arr.get(i - 1), 1); } else v.add((arr.get(i - 1) & 1) == 1 ? arr.get(i - 1) / 2 : arr.get(i - 1) / 2 - 1); } int j = 1; int ans = 0; for (int i = 0; i < v.size(); i++) { while (vis.get(j) != 0) j++; if (v.get(i) >= j) j++; else return -1; ans++; } return ans; } // Driver's code public static void main(String[] args) { // Input array List<Integer> arr = new ArrayList<>(Arrays.asList(1, 7)); // Function call System.out.println(makePermutation(2, arr)); }} |
Python3
# Function to make permutationdef makePermutation(n, arr): vis = [0] * (n + 1) arr.sort() v = [] for i in range(1, n + 1): if arr[i - 1] <= n: if vis[arr[i - 1]]: v.append(arr[i - 1] // 2 if arr[i - 1] & 1 else arr[i - 1] // 2 - 1) vis[arr[i - 1]] = 1 else: v.append(arr[i - 1] // 2 if arr[i - 1] & 1 else arr[i - 1] // 2 - 1) j = 1 ans = 0 for i in range(len(v)): while vis[j]: j += 1 if v[i] >= j: j += 1 else: return -1 ans += 1 return ans# Driver's codeif __name__ == '__main__': # Input array arr = [1, 7] # Function call print(makePermutation(2, arr))# akashish__ |
C#
using System;using System.Collections.Generic;using System.Linq;class GFG{ static int MakePermutation(int n, List<int> arr) { // Initialize a list to keep track of visited elements List<int> vis = new List<int>(new int[n + 1]); // Sort the input array arr.Sort(); // Create a list to store modified values List<int> v = new List<int>(); // Iterate over the input array for (int i = 1; i <= n; i++) { // Check if the current element is within the range if (arr[i - 1] <= n) { // If the element is already visited, add the modified // value to v if (vis[arr[i - 1]] != 0) v.Add((arr[i - 1] & 1) != 0 ? arr[i - 1] / 2 : arr[i - 1] / 2 - 1); // Mark the element as visited vis[arr[i - 1]] = 1; } else { // Add the modified value to v v.Add((arr[i - 1] & 1) != 0 ? arr[i - 1] / 2 : arr[i - 1] / 2 - 1); } } int j = 1; int ans = 0; // Iterate over the modified values in v for (int i = 0; i < v.Count; i++) { // Find the next available element while (vis[j] != 0) j++; // Check if the current modified value is greater // than or equal to the next available element if (v[i] >= j) j++; else return -1; // Increment the answer count ans++; } return ans; } static void Main(string[] args) { // Input array List<int> arr = new List<int> { 1, 7 }; // Function call Console.WriteLine(MakePermutation(2, arr)); }} |
Javascript
function makePermutation(n, arr) { const vis = new Array(n + 1).fill(0); arr.sort((a, b) => a - b); const v = []; for (let i = 1; i <= n; i++) { if (arr[i - 1] <= n) { if (vis[arr[i - 1]]) { v.push(arr[i - 1] & 1 ? arr[i - 1] / 2 : arr[i - 1] / 2 - 1); } vis[arr[i - 1]] = 1; } else { v.push(arr[i - 1] & 1 ? arr[i - 1] / 2 : arr[i - 1] / 2 - 1); } } let j = 1; let ans = 0; for (let i = 0; i < v.length; i++) { while (vis[j]) { j++; } if (v[i] >= j) { j++; } else { return -1; } ans++; } return ans;}// Driver's codeconst arr = [1, 7];console.log(makePermutation(2, arr)); |
Output
1
Time Complexity: O(N*log(N))
Auxiliary Space: O(N)
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Share your thoughts in the comments
