Dada una array arr[] de N enteros, la tarea es encontrar un valor K tal que la operación arr[ i ] = arr[ i ] % K (0 ≤ i ≤ N-1), haga que la array sea una permutación . Si no existe tal K imprima -1.
Una secuencia de N enteros se llama permutación si contiene todos los enteros del 1 al N exactamente una vez.
Ejemplos:
Entrada: N = 3, arr[ ] = {2, 7, 1}
Salida: 4
Explicación: [2%4, 7%4, 1%4] = [2, 3, 1] que es una permutación de N = 3.Entrada: N = 5, arr[ ] = {18, 81, 29, 36, 11}
Salida: 8
Explicación: [18%8, 81%8, 29%8, 36%8, 11%8] = [2 , 1, 5, 4, 3] que es una permutación de N = 5.Entrada: N = 2, arr[ ] = {2, 2}
Salida: -1
Enfoque: El problema dado se puede resolver con la ayuda de la siguiente observación:
Si el arr[] dado tiene al menos un elemento repetido, nunca puede convertirse en una permutación. Entonces, todos los arr[i] deben ser únicos en arr[] . Si no, imprima -1.
Si existe tal K . Entonces, expresamos cada arr[i] en términos de K como se da:
- UNA 1 = Q 1 *K + R 1
UNA 2 = Q 2 *K + R 2
UNA 3 = Q 3 *K + R 3
. . . . . .
UN norte = Q norte * K + R norte- Para ser una K válida, (R1, R2, R3…. RN) debe ser una permutación de 1 a N.
- Por lo tanto, Σ arr[i] = (Σ Q i )*K + (Σ R i ).
- Sabemos (Σ R i ) = (N*(N+1))/2 = S r (Di).
- sea S = (Q’) *K +Sr, donde Q’ = (Σ Qi) .
- sea S rem = (Q’) *K = S – Sr = (suma de todos los elementos del arreglo) – (N*(N+1))/2.
- Es evidente que K debe ser un divisor de S rem .
Siga los pasos que se mencionan a continuación para resolver el problema:
- Comprobar Si arr[] ya es una permutación , entonces una posible respuesta será simplemente (N+1) .
- De lo contrario, encuentre la suma de todos los elementos de la array.
- Encuentre todos los divisores de S rem y verifique cuál de los divisores satisface la condición de que realiza la permutación de la array al aplicar la operación de módulo dada.
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 check is given set a
// permutation
bool is_given_set_permutation(set<int>&
hash,
int N)
{
int last_element = *hash.rbegin();
if (hash.size() == N
&& last_element == N) {
return true;
}
return false;
}
// Function to find the divisors
vector<int> findDivisors(int n)
{
// Note that this loop runs till
// square root
vector<int> divisors;
for (int i = 1; i <= sqrt(n); i++) {
if (n % i == 0) {
// If divisors are equal,
// push only one
if (n / i == i)
divisors.push_back(i);
// Otherwise push both
else {
divisors.push_back(i);
divisors.push_back(n / i);
}
}
}
return divisors;
}
// Function returns if the current divisor
// is the required answer
bool is_current_divisor_answer(int arr[],
int N, int div)
{
set<int> hash;
for (int i{ 0 }; i < N; i++) {
hash.insert(arr[i] % div);
}
return is_given_set_permutation(hash, N);
}
// Function to the number d which on applying
// arr[i]%d to each element makes the array
// a permutation
int number_to_make_permutation(int arr[], int N)
{
// Set to store elements of arr[]
set<int> hash;
for (int i{ 0 }; i < N; i++) {
hash.insert(arr[i]);
}
if (hash.size() != N) {
// When hash size !=N, there are
// repeating elements in arr[].
// So it can never be a permutation
return -1;
}
if (is_given_set_permutation(hash, N)) {
// Given arr[] is already a
// permutation
return (N + 1);
}
int total_sum{ 0 };
// Loop to find the sum of the array
for (int i{ 0 }; i < N; i++) {
total_sum += arr[i];
}
int sum_of_permutation
= (N * (N + 1)) / 2;
int remaining_sum = total_sum - sum_of_permutation;
vector<int> divisors = findDivisors(
remaining_sum);
// Loop to check if any divisor
// satisfies the condition
for (int i{ 0 }; i < divisors.size();
i++) {
// A divisor <= N can
// never be an answer
if (divisors[i] <= N)
continue;
if (is_current_divisor_answer(arr, N,
divisors[i])) {
return divisors[i];
}
}
return -1;
}
// Driver code
int main()
{
int arr[] = { 18, 81, 29, 36, 11 };
int N = sizeof(arr) / sizeof(int);
// Function call
cout << number_to_make_permutation(arr, N);
return 0;
}
Java
import java.util.*;
import java.io.*;
// Java program for the above approach
class GFG{
// Function to check is given set a
// permutation
public static Boolean is_given_set_permutation(SortedSet<Integer> hash, int N)
{
int last_element = hash.last();
if (hash.size() == N && last_element == N) {
return true;
}
return false;
}
// Function to find the divisors
public static ArrayList<Integer> findDivisors(int n)
{
// Note that this loop runs till
// square root
ArrayList<Integer> divisors = new ArrayList<Integer>();
for (int i = 1 ; i <= Math.floor(Math.sqrt(n)) ; i++) {
if (n % i == 0) {
// If divisors are equal,
// push only one
if (n / i == i)
divisors.add(i);
// Otherwise push both
else {
divisors.add(i);
divisors.add(n / i);
}
}
}
return divisors;
}
// Function returns if the current divisor
// is the required answer
public static Boolean is_current_divisor_answer(int arr[], int N, int div)
{
SortedSet<Integer> hash = new TreeSet<Integer>();
for (int i = 0 ; i < N ; i++) {
hash.add(arr[i] % div);
}
return is_given_set_permutation(hash, N);
}
// Function to the number d which on applying
// arr[i]%d to each element makes the array
// a permutation
public static int number_to_make_permutation(int arr[], int N){
// Set to store elements of arr[]
SortedSet<Integer> hash = new TreeSet<Integer>();
for (int i = 0 ; i < N ; i++) {
hash.add(arr[i]);
}
if (hash.size() != N) {
// When hash size !=N, there are
// repeating elements in arr[].
// So it can never be a permutation
return -1;
}
if (is_given_set_permutation(hash, N)) {
// Given arr[] is already a
// permutation
return (N + 1);
}
int total_sum = 0;
// Loop to find the sum of the array
for (int i = 0 ; i < N ; i++) {
total_sum += arr[i];
}
int sum_of_permutation = (N * (N + 1)) / 2;
int remaining_sum = total_sum - sum_of_permutation;
ArrayList<Integer> divisors = findDivisors(remaining_sum);
// Loop to check if any divisor
// satisfies the condition
for (int i = 0 ; i < divisors.size(); i++) {
// A divisor <= N can
// never be an answer
if (divisors.get(i) <= N)
continue;
if (is_current_divisor_answer(arr, N, divisors.get(i))) {
return divisors.get(i);
}
}
return -1;
}
// Driver code
public static void main(String args[])
{
int arr[] = {18, 81, 29, 36, 11};
int N = arr.length;
System.out.println(number_to_make_permutation(arr, N));
}
}
// This code is contributed by subhamgoyal2014.
Python3
# Python3 code to implement above approach import math # Function to check is given set a # permutation def is_given_set_permutation(hash, N): last_element = list(hash)[len(hash) - 1] if (len(hash) == N and last_element == N): return True return False # Function to find the divisors def findDivisors(n): # Note that this loop runs till # square root divisors = [] for i in range(1, int(math.sqrt(n)) + 1): if (n % i == 0): # If divisors are equal, # push only one if (n // i == i): divisors.append(i) # Otherwise push both else: divisors.append(i) divisors.append(n // i) return divisors # Function returns if the current divisor # is the required answer def is_current_divisor_answer(arr, N, div): hash = set() for i in range(0, N): hash.add(arr[i] % div) return is_given_set_permutation(hash, N) # Function to the number d which on applying # arr[i]%d to each element makes the array # a permutation def number_to_make_permutation(arr, N): # Set to store elements of arr[] hash = set() for i in range(0, N): hash.add(arr[i]) if (len(hash) != N): # When hash size !=N, there are # repeating elements in arr[]. # So it can never be a permutation return -1 if (is_given_set_permutation(hash, N)): # Given arr[] is already a # permutation return (N + 1) total_sum = 0 # Loop to find the sum of the array for i in range(0, N): total_sum += arr[i] sum_of_permutation = (N * (N + 1)) // 2 remaining_sum = total_sum - sum_of_permutation divisors = findDivisors(remaining_sum) # Loop to check if any divisor # satisfies the condition for i in range(0, len(divisors)): # A divisor <= N can # never be an answer if (divisors[i] <= N): continue if (is_current_divisor_answer(arr, N, divisors[i])): return divisors[i] return -1 # Driver code if __name__ == "__main__": arr = [18, 81, 29, 36, 11] N = len(arr) # Function call print(number_to_make_permutation(arr, N)) # This code is contributed by rakeshsahni
Producción
8
Complejidad Temporal: O(N * F), donde F es el número máximo de divisores.
Espacio Auxiliar: O(N)
Publicación traducida automáticamente
Artículo escrito por anilyogi2801 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA