Dada una array arr[] que consta de N enteros positivos y los enteros X y M , donde 0 <= X < M , la tarea es encontrar el número mínimo de elementos necesarios para eliminar tal que la suma de la array restante módulo M sea igual a X. Imprima -1 si no es posible.
Ejemplos:
Entrada: arr[] = {3, 2, 1, 2}, M = 4, X = 2
Salida: 1
Explicación: Uno de los elementos en los índices (basado en 0) 1 o 3 se puede eliminar. Si se elimina arr[1], entonces arr[] se modifica a {3, 1, 2} y suma % M = 6 % 4 = 2, que es igual a X = 2.Entrada: arr[] = {3, 2, 1, 3}, M = 4, X = 3
Salida: 1
Explicación: Eliminar elemento arr[1]( = 2). Por lo tanto, arr[] se modifica a {3, 1, 3} y suma % M = 7 % 4 = 3 que es igual a X = 3.
Enfoque ingenuo: el enfoque más simple es generar todos los subconjuntos posibles de la array dada y, para cada subconjunto, verificar si la suma del módulo M de la array después de la eliminación del subconjunto es igual a X o no. Si se encuentra que es cierto, almacene su tamaño. Imprime el tamaño mínimo entre todos los subconjuntos obtenidos.
Complejidad de tiempo: O(2 N ) donde N es la longitud de la array dada.
Espacio Auxiliar: O(N)
Enfoque eficiente: para optimizar el enfoque anterior, la idea es utilizar programación dinámica basada en las siguientes observaciones:
- Si S % M > X , entonces el número mínimo de elementos que tienen la suma S % M – X debe eliminarse de la array para hacer que la suma módulo M sea igual a X .
- De lo contrario, se debe eliminar el número mínimo de elementos que tienen suma S % M + M – X para que la suma módulo M sea igual a X .
Siga los pasos a continuación para resolver el problema:
- Inicialice una tabla dp[] , table[N + 1][X + 1] donde table[i][j] representa el número mínimo de elementos a eliminar que tienen índices en el rango [0, i] tal que su suma sea j donde X es la suma por lo que se elimina.
- Inicialice dp[0][i] para cada i en el rango [1, X] con un valor grande.
- Las transiciones dp son las siguientes:
dp[i][j] = min(dp[i-1][j], dp[i][j-arr[i-1]]+1)
donde i está en el rango [1, N] y j está en el rango [1, X] .
- Imprima dp[N][X] como los elementos mínimos a eliminar.
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 find the minimum // elements having sum x int findSum(vector<int> S, int n, int x) { // Initialize dp table vector<vector<int> > table(n + 1, vector<int>( x + 1, 0)); for (int i = 1; i <= x; i++) { table[0][i] = INT_MAX - 1; } // Pre-compute subproblems for (int i = 1; i <= n; i++) { for (int j = 1; j <= x; j++) { // If mod is smaller than element if (S[i - 1] > j) { table[i][j] = table[i - 1][j]; } else { // Minimum elements with sum // j upto index i table[i][j] = min(table[i - 1][j], table[i][j - S[i - 1]] + 1); } } } // Return answer return (table[n][x] > n) ? -1 : table[n][x]; } // Function to find minimum number // of removals to make sum % M in // remaining array is equal to X void minRemovals(vector<int> arr, int n, int m, int x) { // Sum of all elements int sum = 0; for (int i = 0; i < n; i++) { sum += arr[i]; } // Sum to be removed int requied_Sum = 0; if (sum % m < x) requied_Sum = m + sum % m - x; else requied_Sum = sum % m - x; // Print answer cout << findSum(arr, n, requied_Sum); } // Driver Code int main() { // Given array vector<int> arr = { 3, 2, 1, 2 }; // Given size int n = arr.size(); // Given mod and x int m = 4, x = 2; // Function call minRemovals(arr, n, m, x % m); return 0; }
Java
// Java program for the above approach import java.util.*; class GFG{ // Function to find the minimum // elements having sum x static int findSum(int[] S, int n, int x) { // Initialize dp table int [][]table = new int[n + 1][x + 1]; for(int i = 1; i <= x; i++) { table[0][i] = Integer.MAX_VALUE - 1; } // Pre-compute subproblems for(int i = 1; i <= n; i++) { for(int j = 1; j <= x; j++) { // If mod is smaller than element if (S[i - 1] > j) { table[i][j] = table[i - 1][j]; } else { // Minimum elements with sum // j upto index i table[i][j] = Math.min(table[i - 1][j], table[i][j - S[i - 1]] + 1); } } } // Return answer return (table[n][x] > n) ? -1 : table[n][x]; } // Function to find minimum number // of removals to make sum % M in // remaining array is equal to X static void minRemovals(int[] arr, int n, int m, int x) { // Sum of all elements int sum = 0; for(int i = 0; i < n; i++) { sum += arr[i]; } // Sum to be removed int requied_Sum = 0; if (sum % m < x) requied_Sum = m + sum % m - x; else requied_Sum = sum % m - x; // Print answer System.out.print(findSum(arr, n, requied_Sum)); } // Driver Code public static void main(String[] args) { // Given array int[] arr = { 3, 2, 1, 2 }; // Given size int n = arr.length; // Given mod and x int m = 4, x = 2; // Function call minRemovals(arr, n, m, x % m); } } // This code is contributed by Amit Katiyar
Python3
# Python3 program for the above approach import sys # Function to find the minimum # elements having sum x def findSum(S, n, x): # Initialize dp table table = [[0 for x in range(x + 1)] for y in range(n + 1)] for i in range(1, x + 1): table[0][i] = sys.maxsize - 1 # Pre-compute subproblems for i in range(1, n + 1): for j in range(1, x + 1): # If mod is smaller than element if (S[i - 1] > j): table[i][j] = table[i - 1][j] else: # Minimum elements with sum # j upto index i table[i][j] = min(table[i - 1][j], table[i][j - S[i - 1]] + 1) # Return answer if (table[n][x] > n): return -1 return table[n][x] # Function to find minimum number # of removals to make sum % M in # remaining array is equal to X def minRemovals(arr, n, m, x): # Sum of all elements sum = 0 for i in range(n): sum += arr[i] # Sum to be removed requied_Sum = 0 if (sum % m < x): requied_Sum = m + sum % m - x else: requied_Sum = sum % m - x # Print answer print(findSum(arr, n, requied_Sum)) # Driver Code if __name__ == "__main__": # Given array arr = [ 3, 2, 1, 2 ] # Given size n = len(arr) # Given mod and x m = 4 x = 2 # Function call minRemovals(arr, n, m, x % m) # This code is contributed by chitranayal
C#
// C# program for the // above approach using System; class GFG{ // Function to find the minimum // elements having sum x static int findSum(int[] S, int n, int x) { // Initialize dp table int [,]table = new int[n + 1, x + 1]; for(int i = 1; i <= x; i++) { table[0, i] = int.MaxValue - 1; } // Pre-compute subproblems for(int i = 1; i <= n; i++) { for(int j = 1; j <= x; j++) { // If mod is smaller than // element if (S[i - 1] > j) { table[i, j] = table[i - 1, j]; } else { // Minimum elements with sum // j upto index i table[i, j] = Math.Min(table[i - 1, j], table[i, j - S[i - 1]] + 1); } } } // Return answer return (table[n, x] > n) ? -1 : table[n, x]; } // Function to find minimum number // of removals to make sum % M in // remaining array is equal to X static void minRemovals(int[] arr, int n, int m, int x) { // Sum of all elements int sum = 0; for(int i = 0; i < n; i++) { sum += arr[i]; } // Sum to be removed int requied_Sum = 0; if (sum % m < x) requied_Sum = m + sum % m - x; else requied_Sum = sum % m - x; // Print answer Console.Write(findSum(arr, n, requied_Sum)); } // Driver Code public static void Main(String[] args) { // Given array int[] arr = {3, 2, 1, 2}; // Given size int n = arr.Length; // Given mod and x int m = 4, x = 2; // Function call minRemovals(arr, n, m, x % m); } } // This code is contributed by Amit Katiyar
Javascript
<script> // JavaScript program to implement // the above approach // Function to find the minimum // elements having sum x function findSum(S, n, x) { // Initialize dp table let table = new Array(n + 1); // Loop to create 2D array using 1D array for (var i = 0; i < table.length; i++) { table[i] = new Array(2); } for (var i = 0; i < table.length; i++) { for (var j = 0; j < table.length; j++) { table[i][j] = 0; } } for(let i = 1; i <= x; i++) { table[0][i] = Number.MAX_VALUE - 1; } // Pre-compute subproblems for(let i = 1; i <= n; i++) { for(let j = 1; j <= x; j++) { // If mod is smaller than element if (S[i - 1] > j) { table[i][j] = table[i - 1][j]; } else { // Minimum elements with sum // j upto index i table[i][j] = Math.min(table[i - 1][j], table[i][j - S[i - 1]] + 1); } } } // Return answer return (table[n][x] > n) ? -1 : table[n][x]; } // Function to find minimum number // of removals to make sum % M in // remaining array is equal to X function minRemovals(arr, n, m, x) { // Sum of all elements let sum = 0; for(let i = 0; i < n; i++) { sum += arr[i]; } // Sum to be removed let requied_Sum = 0; if (sum % m < x) requied_Sum = m + sum % m - x; else requied_Sum = sum % m - x; // Print answer document.write(findSum(arr, n, requied_Sum)); } // Driver Code // Given array let arr = [ 3, 2, 1, 2 ]; // Given size let n = arr.length; // Given mod and x let m = 4, x = 2; // Function call minRemovals(arr, n, m, x % m); </script>
1
Complejidad de tiempo: O(N*X) donde N es la longitud de la array dada y X es el número entero dado.
Espacio Auxiliar: O(N*X)
Publicación traducida automáticamente
Artículo escrito por mohit kumar 29 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA