Dados dos enteros N , Y , genere una permutación de longitud N tal que la suma de todos los prefijos mínimos de esa permutación sea Y .
Ejemplo:
Entrada: N = 5, Y = 10
Salida: 5 2 1 4 3
Explicación: La array de prefijos mínimos para [5, 2, 1, 4, 3] es [5, 2, 1, 1, 1]. La suma de esta array de prefijos mínimos es 10 (= Y).Entrada: N = 5, Y = 5
Salida: 1 2 3 4 5
Explicación: La array de prefijos mínimos para [1, 2, 3, 4, 5] es [1, 1, 1, 1, 1]. La suma de esta array de prefijos mínimos es 5 (= Y).
Enfoque: El enfoque para resolver este problema se basa en la siguiente idea:
Suponga que la array restante que se creará en algún momento sea len y la suma restante sea rem .
Elija con avidez un valor para este índice mediante el siguiente método:
- tomemos el valor Z en este índice, entonces deberíamos tener al menos (Z + len – 1) = rem (Tomando 1 en los índices restantes).
- Entonces, obtenemos Z = (rem + 1 – len). Ahora, este valor puede ser mayor que len, pero no podemos aceptarlo. Entonces, elegiremos min(Z, len).
Siga los pasos a continuación para resolver este problema:
- Ahora, una array mínima de prefijo para la permutación requerida ya está construida a partir del método codicioso anterior.
- También podría tener duplicados. Entonces, para eliminar esa iteración sobre esta array en orden inverso y siempre que arr[i] = arr[i-1], coloque el elemento más pequeño que no esté presente en ningún índice en el i -ésimo índice.
- De esta manera, se aseguró de que la suma del mínimo de prefijos sea Y y la array creada también sea una permutación.
- Imprimir la array final
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program for Generate permutation // of length N such that sum of all prefix // minimum of that permutation is Y. #include <iostream> #include <set> #include <vector> using namespace std; // Find the value greedily for the // current index as discussed in approach int findValue(long long N, long long Y) { return min(N, Y + 1 - N); } // Function to generate the permutation void generatePermutation(long long N, long long Y) { // Store the prefix minimum array first // then we will convert it to permutation vector<int> ans(N); // If Y should belong to [N, (N*(N + 1)/2)], // otherwise we will print -1; if (Y < N || (2 * Y) > (N * (N + 1))) { cout << -1 << endl; return; } // Remaining elements to be taken set<int> s; for (int i = 1; i <= N; i++) { s.insert(i); } // Generate prefix minimum array for (int i = 0; i < N; i++) { // Length remaining int len = N - i; int val = findValue(len, Y); ans[i] = val; Y -= val; if (s.find(val) != s.end()) s.erase(val); } // Remove duplicates to make array permutation // So, iterate in reverse order for (int i = N - 1; i > 0; i--) { if (ans[i] == ans[i - 1]) { // Find minimum element not taken // in the permutation ans[i] = *s.begin(); s.erase(ans[i]); } } // Print the permutation for (auto i : ans) { cout << i << " "; } cout << endl; } // Driver Code int main() { long long N = 5, Y = 10; generatePermutation(N, Y); return 0; }
Java
// Java program for Generate permutation // of length N such that sum of all prefix // minimum of that permutation is Y. import java.util.*; class GFG { // Find the value greedily for the // current index as discussed in approach static int findValue(int N, int Y) { return Math.min(N, Y + 1 - N); } // Function to generate the permutation static void generatePermutation( int N, int Y) { // Store the prefix minimum array first // then we will convert it to permutation int[] ans = new int[N]; // If Y should belong to [N, (N*(N + 1)/2)], // otherwise we will print -1; if (Y < N || (2 * Y) > (N * (N + 1))) { System.out.println(-1); return; } // Remaining elements to be taken Set<Integer> s = new HashSet<Integer>(); for (int i = 1; i <= N; i++) { s.add(i); } // Generate prefix minimum array for (int i = 0; i < N; i++) { // Length remaining int len = N - i; int val = findValue(len, Y); ans[i] = val; Y -= val; if (s.contains(val)) s.remove(val); } // Remove duplicates to make array permutation // So, iterate in reverse order for (int i = N - 1; i > 0; i--) { if (ans[i] == ans[i - 1]) { // Find minimum element not taken // in the permutation ans[i] = s.stream().findFirst().get(); s.remove(ans[i]); } } // Print the permutation for (int i = 0; i < N; i++) { System.out.print(ans[i] + " "); } } // Driver Code public static void main (String[] args) { int N = 5, Y = 10; generatePermutation(N, Y); } } // This code is contributed by hrithikgarg03188.
Python3
# python3 program for Generate permutation # of length N such that sum of all prefix # minimum of that permutation is Y. # Find the value greedily for the # current index as discussed in approach def findValue(N, Y): return min(N, Y + 1 - N) # Function to generate the permutation def generatePermutation(N, Y): # Store the prefix minimum array first # then we will convert it to permutation ans = [0 for _ in range(N)] # If Y should belong to [N, (N*(N + 1)/2)], # otherwise we will print -1; if (Y < N or (2 * Y) > (N * (N + 1))): print(-1) return # Remaining elements to be taken s = set() for i in range(1, N+1): s.add(i) # Generate prefix minimum array for i in range(0, N): # Length remaining len = N - i val = findValue(len, Y) ans[i] = val Y -= val if (val in s): s.remove(val) # Remove duplicates to make array permutation # So, iterate in reverse order for i in range(N-1, -1, -1): if (ans[i] == ans[i - 1]): # Find minimum element not taken # in the permutation ans[i] = list(s)[0] s.remove(ans[i]) # Print the permutation for i in ans: print(i, end=" ") print() # Driver Code if __name__ == "__main__": N, Y = 5, 10 generatePermutation(N, Y) # This code is contributed by rakeshsahni
C#
// C# implementation of above approach using System; using System.Collections.Generic; using System.Linq; class GFG{ // Find the value greedily for the // current index as discussed in approach static int findValue(int N, int Y) { return Math.Min(N, Y + 1 - N); } // Function to generate the permutation static void generatePermutation( int N, int Y) { // Store the prefix minimum array first // then we will convert it to permutation int[] ans = new int[N]; // If Y should belong to [N, (N*(N + 1)/2)], // otherwise we will print -1; if (Y < N || (2 * Y) > (N * (N + 1))) { Console.Write(-1); return; } // Remaining elements to be taken HashSet<int> s = new HashSet<int>(); for (int i = 1; i <= N; i++) { s.Add(i); } // Generate prefix minimum array for (int i = 0; i < N; i++) { // Length remaining int len = N - i; int val = findValue(len, Y); ans[i] = val; Y -= val; if (s.Contains(val)) s.Remove(val); } // Remove duplicates to make array permutation // So, iterate in reverse order for (int i = N - 1; i > 0; i--) { if (ans[i] == ans[i - 1]) { // Find minimum element not taken // in the permutation ans[i] = s.First(); s.Remove(ans[i]); } } // Print the permutation for (int i = 0; i < N; i++) { Console.Write(ans[i] + " "); } } // Driver Code static public void Main (){ int N = 5, Y = 10; generatePermutation(N, Y); } } // This code is contributed by code_hunt.
Javascript
<script> // JavaScript program for Generate permutation // of length N such that sum of all prefix // minimum of that permutation is Y. // Find the value greedily for the // current index as discussed in approach function findValue(N, Y) { return Math.min(N, Y + 1 - N); } // Function to generate the permutation function generatePermutation(N, Y) { // Store the prefix minimum array first // then we will convert it to permutation let ans = new Array(N); // If Y should belong to [N, (N*(N + 1)/2)], // otherwise we will print -1; if (Y < N || (2 * Y) > (N * (N + 1))) { document.write(-1,"</br>"); return; } // Remaining elements to be taken let s = new Set(); for (let i = 1; i <= N; i++) { s.add(i); } // Generate prefix minimum array for (let i = 0; i <N; i++) { // Length remaining let len = N - i; let val = findValue(len, Y); ans[i] = val; Y -= val; if (s.has(val)) s.delete(val); } // Remove duplicates to make array permutation // So, iterate in reverse order for (let i = N - 1; i > 0; i--) { if (ans[i] == ans[i - 1]) { // Find minimum element not taken // in the permutation ans[i] = Array.from(s)[0] s.delete(ans[i]); } } // Print the permutation for (let i of ans) { document.write(i," "); } document.write("</N;>"); } // Driver Code let N = 5, Y = 10; generatePermutation(N, Y); // This code is contributed by shinjanpatra </script>
5 2 1 4 3
Complejidad temporal: O(N * log N).
Si estamos usando un conjunto, podemos convertirlo en O(N) usando la técnica de dos punteros.
Espacio Auxiliar: O(N)
Publicación traducida automáticamente
Artículo escrito por subhamgoyal2014 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA