Given an array arr[] of size N, the task is to find the minimum number of operations to convert the array into a permutation of [1, n], in each operation, an element a[i] can be replaced by a[i] % d where d can be different in each operation performed. If it is not possible print -1.
Examples:
Input: arr[] = {5, 4, 10, 8, 1}
Output: 2
Explanation: In first operation choosing d = 7 , 10 can be replaced by 10 % 7 ,
In second operation d = 6, 8 can be replaced by 8 %6 so two operations.Input : arr[] = {1, 2, 3, 7}
Output: -1
Approach: The task can be solved using the greedy approach. This approach is based on the fact that when remainder r is to be obtained, then a[i] > 2*r i.e r lies between the range [0, a[i]-1 /2]
Let us take an example: 8 for different d
Taking, 8 % 7= 1
8%6 = 2
8%5 = 3
8%4 = 0
8%3 = 2
8%2 = 0
8%1=0
So maximum number that can be obtained is 3 using mod operation, so when we want to obtain a number i in a permutation then the number should a[i] > 2* i+1
Follow these steps to solve this problem:
- Initialize a set s
- Traverse through the array arr[] & insert all the elements of arr[] into the set.
- Initialize a variable ops = 0
- Now iterate from n to 1
- Check if s has i already if it has removed it from the set.
- Else increment ops and check if the largest element of the set < 2* i +1
- If the largest of the set is < 2* i +1 then set ops = -1 and break out of the loop.
- Else erase it from the set because we can make it i using mod operation.
- Print the ops
`Below is the implementation of the above approach:
C++
// C++ code for the above approach#include <bits/stdc++.h>using namespace std;// Function to find the minimum operations// to convert the array into a permutation of [1, n]void minimum_operations(int arr[], int n){ // Initialize the set set<int> s; // Insert all the elements into the set for (int i = 0; i < n; i++) { s.insert(arr[i]); } // Initialize ops to count the operations int ops = 0; // Traverse from [n to 1] for (int i = n; i >= 1; i--) { // If we already have i in our // array erase it from the set if (s.find(i) != s.end()) { s.erase(s.find(i)); } // count the ops because there is no element else { ops++; // Check the largest element of the set auto it = s.end(); it--; // If it is < 2*i +1 we cant get that i // using % operation so there is no way to // create a permutation if (*it < 2 * i + 1) { ops = -1; break; } // Erase it if we have processed // it to i by % operation s.erase(it); } } // Print the result cout << ops << endl;}// Driver Codeint main(){ // Initialize the value n int arr[] = { 5, 4, 10, 8, 1 }; int n = sizeof(arr) / sizeof(arr[0]); minimum_operations(arr, n); return 0;} |
Java
// Java code for the above approachimport java.util.*;class GFG{ // Function to find the minimum operations // to convert the array into a permutation of [1, n] static void minimum_operations(int arr[], int n) { // Initialize the set SortedSet<Integer> s = new TreeSet<Integer>(); // Insert all the elements into the set for (int i = 0; i < n; i++) { s.add(arr[i]); } // Initialize ops to count the operations int ops = 0; // Traverse from [n to 1] for (int i = n; i >= 1; i--) { // If we already have i in our // array erase it from the set if (s.contains(i)) { s.remove(i); } // count the ops because there is no element else { ops++; // Check the largest element of the set Integer it = s.last(); it--; // If it is < 2*i +1 we cant get that i // using % operation so there is no way to // create a permutation if (it < 2 * i + 1) { ops = -1; break; } // Erase it if we have processed // it to i by % operation s.remove(it); } } // Print the result System.out.print(ops +"\n"); } // Driver Code public static void main(String[] args) { // Initialize the value n int arr[] = { 5, 4, 10, 8, 1 }; int n = arr.length; minimum_operations(arr, n); }}// This code is contributed by 29AjayKumar |
Python3
# Python 3 code for the above approach# Function to find the minimum operations# to convert the array into a permutation of [1, n]def minimum_operations(arr, n): # Initialize the set s = set([]) # Insert all the elements into the set for i in range(n): s.add(arr[i]) # Initialize ops to count the operations ops = 0 # Traverse from [n to 1] for i in range(n, 0, -1): # If we already have i in our # array erase it from the set if (i in s): list(s).remove(i) # count the ops because there is no element else: ops += 1 # Check the largest element of the set it = len(s) it -= 1 # If it is < 2*i +1 we cant get that i # using % operation so there is no way to # create a permutation if (list(s)[it] < 2 * i + 1): ops = -1 break # Erase it if we have processed # it to i by % operation list(s).pop(it) # Print the result print(ops)# Driver Codeif __name__ == "__main__": # Initialize the value n arr = [5, 4, 10, 8, 1] n = len(arr) minimum_operations(arr, n) # This code is contributed by ukasp. |
C#
// C# code for the above approachusing System;using System.Collections.Generic;public class GFG{ // Function to find the minimum operations // to convert the array into a permutation of [1, n] static void minimum_operations(int []arr, int n) { // Initialize the set SortedSet<int> s = new SortedSet<int>(); // Insert all the elements into the set for (int i = 0; i < n; i++) { s.Add(arr[i]); } // Initialize ops to count the operations int ops = 0; // Traverse from [n to 1] for (int i = n; i >= 1; i--) { // If we already have i in our // array erase it from the set if (s.Contains(i)) { s.Remove(i); } // count the ops because there is no element else { ops++; // Check the largest element of the set int it = s.Max; it--; // If it is < 2*i +1 we cant get that i // using % operation so there is no way to // create a permutation if (it < 2 * i + 1) { ops = -1; break; } // Erase it if we have processed // it to i by % operation s.Remove(it); } } // Print the result Console.Write(ops +"\n"); } // Driver Code public static void Main(String[] args) { // Initialize the value n int []arr = { 5, 4, 10, 8, 1 }; int n = arr.Length; minimum_operations(arr, n); }}// This code is contributed by 29AjayKumar |
Javascript
<script>// Javascript code for the above approach// Function to find the minimum operations// to convert the array into a permutation of [1, n]function minimum_operations(arr, n){ // Initialize the set var s = new Set(); // Insert all the elements into the set for (var i = 0; i < n; i++) { s.add(arr[i]); } // Initialize ops to count the operations var ops = 0; // Traverse from [n to 1] for (var i = n; i >= 1; i--) { // If we already have i in our // array erase it from the set if (s.has(i)) { s.delete(i); } // count the ops because there is no element else { ops++; // Check the largest element of the set var it = Math.max(...Array.from(s.values())); it--; // If it is < 2*i +1 we cant get that i // using % operation so there is no way to // create a permutation if (it < 2 * i + 1) { ops = -1; break; } // Erase it if we have processed // it to i by % operation s.delete(it); } } // Print the result document.write(ops +"<br>");}// Driver Code// Initialize the value nvar arr = [ 5, 4, 10, 8, 1 ];var n = arr.length;minimum_operations(arr, n);// This code is contributed by Shubham Singh </script> |
Output
2
Time Complexity: O(nlogn)
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!
