Compruebe si los elementos de la array dada se pueden reorganizar de manera que (arr[i] + i*K) % N = i para todos los valores de i en el rango [0, N-1]

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++ 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 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

<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)