Dada una array arr[] que consta de N enteros positivos y un entero K , la tarea es verificar si los elementos de la array se pueden reorganizar de modo que (arr[i] + i*K) % N = i para todos los valores de i en el rango [0, N-1] .
Ejemplos:
Entrada: arr[] = {2, 1, 0}, K = 5
Salida: Sí
Explicación: La array dada se puede reorganizar a {0, 2, 1}. Por lo tanto, los valores después de la actualización se convierten en {(0 + 0*5) % 3, (2 + 1*5) % 3, (1 + 2*5) % 3} => {0%3, 7%3, 11% 3} => {0, 1, 2} que tiene todos los elementos iguales a sus índices en la array.Entrada: arr[] = {1, 1, 1, 1, 1}, K = 5
Salida: No
Enfoque ingenuo: el problema dado se puede resolver generando todas las permutaciones posibles de la array dada arr[] y verificando si existe alguna permutación que satisfaga los criterios dados.
Complejidad temporal: O(N*N!)
Espacio auxiliar: O(N)
Enfoque eficiente: el enfoque anterior también se puede optimizar con la ayuda de la estructura de datos Set usando Recursion . A continuación se presentan algunas observaciones para resolver el problema dado:
- El hecho de que cada elemento de la array arr[i] se actualice como (arr[i] + i*K) % N . Entonces, el valor arr[i] % N e i*K % N se pueden calcular de forma independiente.
- Si un conjunto múltiple A contiene todos los valores de arr[i] % N y un conjunto múltiple B contiene todos los valores de i*K % N para todos los valores de i en el rango [0, N-1] , genere todas las combinaciones posibles de elementos en A y B y almacenar (A[i] + B[i]) % N en un conjunto. Si el tamaño del conjunto resultante es N , es posible reorganizar la array de la forma requerida.
Usando las observaciones anteriores, el problema dado se puede resolver mediante los siguientes pasos:
- Cree un conjunto múltiple A que contenga todos los valores de arr[i] % N para todos los valores de i en el rango [0, N-1] .
- De manera similar, cree un conjunto múltiple B que contenga todos los valores de i*K % N para todos los valores de i en el rango [0, N-1] .
- Cree una función recursiva para iterar sobre todos los pares de enteros en A y B , agregue su módulo de suma N en el conjunto C y llame recursivamente a los elementos restantes.
- Si en cualquier punto, el tamaño del conjunto C = N , devuelve verdadero ; de lo contrario, devuelve falso .
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program for the above approach
#include <bits/stdc++.h>
using namespace std;
// Function to check if it is possible
// to generate all numbers in range
// [0, N-1] using the sum of elements
// in the multiset A and B mod N
bool isPossible(multiset<int> A,
multiset<int> B,
set<int> C, int N)
{
// If no more pair of elements
// can be selected
if (A.size() == 0 || B.size() == 0) {
// If the number of elements
// in C = N, then return true
if (C.size() == N) {
return true;
}
// Otherwise return false
else {
return false;
}
}
// Stores the value of final answer
bool ans = false;
// Iterate through all the pairs in
// the given multiset A and B
for (auto x : A) {
for (auto y : B) {
// Stores the set A without x
multiset<int> _A = A;
_A.erase(_A.find(x));
// Stores the set B without y
multiset<int> _B = B;
_B.erase(_B.find(y));
// Stores the set C with (x+y)%N
set<int> _C = C;
_C.insert((x + y) % N);
// Recursive call
ans = (ans
|| isPossible(
_A, _B, _C, N));
}
}
// Return Answer
return ans;
}
// Function to check if it is possible
// to rearrange array elements such that
// (arr[i] + i*K) % N = i
void rearrangeArray(
int arr[], int N, int K)
{
// Stores the values of arr[] modulo N
multiset<int> A;
for (int i = 0; i < N; i++) {
A.insert(arr[i] % N);
}
// Stores all the values of
// i*K modulo N
multiset<int> B;
for (int i = 0; i < N; i++) {
B.insert((i * K) % N);
}
set<int> C;
// Print Answer
if (isPossible(A, B, C, N)) {
cout << "YES";
}
else {
cout << "NO";
}
}
// Driver Code
int main()
{
int arr[] = { 1, 2, 0 };
int K = 5;
int N = sizeof(arr) / sizeof(arr[0]);
rearrangeArray(arr, N, K);
return 0;
}
Python3
# Python3 program for the above approach
# Function to check if it is possible
# to generate all numbers in range
# [0, N-1] using the sum of elements
#+ in the multiset A and B mod N
def isPossible(A, B, C, N):
# If no more pair of elements
# can be selected
if(len(A) == 0 or len(B) == 0):
# If the number of elements
# in C = N, then return true
if(len(C) == N):
return True
# Otherwise return false
else:
return False
# Stores the value of final answer
ans = False
for x in A:
# Iterate through all the pairs in
# the given multiset A and B
for y in B:
# Stores the set A without x
_A = A
_A.remove(x)
# Stores the set A without y
_B = B
_B.remove(y)
# Stores the set A without x+y%N
_C = C
_C.add((x+y) % N)
# Recursive call
ans = (ans or isPossible(_A, _B, _C, N))
return ans
# Function to check if it is possible
# to rearrange array elements such that
# (arr[i] + i*K) % N = i
def rearrangeArray(arr, N, K):
# Stores the values of arr[] modulo N
A = []
for i in range(N):
A.append(arr[i] % N)
A.sort()
# Stores all the values of
# i*K modulo N
B = []
for i in range(N):
B.append((i*K) % N)
B.sort()
C = set()
# Print Answer
if isPossible(A, B, C, N):
print("YES")
else:
print("NO")
# Driver code
arr = [1, 2, 0]
K = 5
N = len(arr)
rearrangeArray(arr, N, K)
# This code is contributed by parthmanchanda81
Javascript
<script>
// JavaScript program for the above approach
// Function to check if it is possible
// to generate all numbers in range
// [0, N-1] using the sum of elements
// + in the multiset A and B mod N
function isPossible(A, B, C, N){
// If no more pair of elements
// can be selected
if(A.length == 0 || B.length == 0){
// If the number of elements
// in C = N, then return true
if(C.size == N)
return true
// Otherwise return false
else
return false
}
// Stores the value of final answer
let ans = false
for(let x of A){
// Iterate through all the pairs in
// the given multiset A and B
for(let y of B){
// Stores the set A without x
let _A = []
_A = A
_A = _A.filter((a)=>a !== x)
// Stores the set A without y
let _B = B
_B = _B.filter((a)=>a !== y)
// Stores the set A without x+y%N
let _C = C
_C.add((x+y) % N)
// Recursive call
ans = ans || isPossible(_A, _B, _C, N)
}
}
return ans
}
// Function to check if it is possible
// to rearrange array elements such that
// (arr[i] + i*K) % N = i
function rearrangeArray(arr, N, K){
// Stores the values of arr[] modulo N
let A = []
for(let i = 0; i < N; i++)
A.push(arr[i] % N)
A.sort()
// Stores all the values of
// i*K modulo N
let B = []
for(let i = 0; i < N; i++)
B.push((i*K) % N)
B.sort()
let C = new Set()
// Print Answer
if(isPossible(A, B, C, N))
document.write("YES")
else
document.write("NO")
}
// Driver code
let arr = [1, 2, 0]
let K = 5
let N = arr.length
rearrangeArray(arr, N, K)
// This code is contributed by shinjanpatra
</script>
YES
Complejidad temporal: O(N*2 N )
Espacio auxiliar: O(1)
Publicación traducida automáticamente
Artículo escrito por kartikey134 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA