Dada una array arr[] de tamaño N , la tarea es encontrar el número mínimo de operaciones requeridas para hacer de la array una permutación de números en el rango [1, N] donde, en cada operación, un elemento en cualquier índice i puede ser reemplazado por arr[i]%k (k = cualquier valor mayor que 0). Devuelve -1 si la array no se puede convertir en una permutación de números en el rango [1, N] .
Ejemplos:
Entrada: arr [] = {1, 7}, N = 2
Salida: 1
Explicación: La única secuencia posible de operaciones que minimiza el número de operaciones es
Elija i = 1, k = 5. Realice arr[1] = arr[ 1] % 5 = 2.Entrada: arr [] = {1,5,4}, N = 3
Salida: -1
Explicación: Es imposible obtener una permutación de números enteros de 1 a N.
Enfoque: El problema se puede resolver sobre la base de la siguiente observación.
x % y < (x/2) si x ≥ y,y
x % y = x six < y .Cuanto mayor sea x , mayor será el rango de valores que se pueden obtener después de una operación de modificación.
Así que intente asignar un arr[i] más pequeño a números más pequeños en la permutación resultante.Aunque, si arr[i] satisface 1 ≤ arr[i] ≤ N , simplemente déjelo ahí y utilícelo en la permutación resultante.
si varios arr[i] satisfacen la misma condición y tienen el mismo valor , simplemente elija uno .
Supongamos que en la solución óptima, l se cambia a myn a l para algunos n > l > m (l, m, n son valores, no índices).
Luego, mantener l intacto y cambiar n a m usa 1 operación menos.
Y, si es posible cambiar n por l , entonces debe ser posible cambiarn a m .
Siga los pasos que se mencionan a continuación para implementar el enfoque:
- Ordenar la array.
- Si 1 ≤ arr[i] ≤ N y es la primera aparición del elemento con valor arr[i], déjalo ahí.
- De lo contrario, deje que el valor actual menos no asignado en la permutación resultante sea x:
- Si x < arr[i]/2 , asigne el elemento actual al valor x y agregue el número de operaciones por 1.
- De lo contrario, genera −1 directamente.
A continuación se muestra la implementación del enfoque anterior.
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 N
void 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 code
int main()
{
int N = 3;
vector<int> arr = { 1, 5, 4 };
minoperation(arr, N);
return 0;
}
Java
// Java code to implement above approach
import 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 approach
using 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 N
def 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 code
if __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
Complejidad temporal: O(N * logN)
Espacio auxiliar: O(N)