Dada una array A[] de tamaño N , la tarea es encontrar el número mínimo de operaciones requeridas para hacer que todos los elementos de la array sean cero . En un paso, las siguientes operaciones se realizan en un subarreglo del arreglo dado:
- Se elige cualquier entero X
- Si un elemento es mayor que X ( A [i] > X ), el elemento de la array se reduce en el valor A[i] – X
- ( A[i] – X ) debe ser igual para todos los elementos que se reducen.
Ejemplos:
Entrada : A[] = {4, 3, 4}, N = 3
Salida : 2
Explicación : Las siguientes operaciones se realizan en el arreglo:
Para la primera operación, elija el arreglo completo como subarreglo, tome X = 3. El arreglo se convierte en A[] = {3, 3, 3}.
Para la segunda operación, elija la array completa como subarreglo, tome X = 0. La array se convierte en A[] = {0, 0, 0}.
Por lo tanto, se requieren 2 pasos para hacer que todos los elementos de A sean iguales a cero.Entrada : A[] = {4, 5, 8, 3, 15, 5, 4, 6, 8, 10, 45}, N = 11
Salida : 8
Enfoque : La tarea se puede resolver utilizando las siguientes observaciones:
- Para satisfacer la última condición, X debe tener un valor tal que los elementos de la array que se reducirán sean todos iguales.
- Para minimizar las operaciones, se debe seleccionar la array total cada vez y se debe elegir X de la siguiente manera:
- Para la primera iteración, X es el segundo número más alto distinto. Para la segunda iteración, X es el tercer número más alto distinto y así sucesivamente
- Por lo tanto, las operaciones totales mínimas serán el recuento de elementos distintos presentes en la array.
Siga los pasos a continuación para resolver el problema anterior:
- Declare un conjunto para almacenar el recuento de elementos únicos.
- Iterar sobre los elementos de la array usando un bucle:
- Si un elemento de la array dice A [i], no es igual a cero, insértelo en el conjunto.
- el tamaño del conjunto denota el número de elementos únicos.
- Devuelve el tamaño del conjunto como respuesta final.
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 number of steps required // to reduce all array elements to zero int minSteps(int A[], int N) { // To store all distinct array elements unordered_set<int> s; // Loop to iterate over the array for (int i = 0; i < N; ++i) { // If an array element is // greater than zero if (A[i] != 0) { // Insert the element // in the set s s.insert(A[i]); } } // Return the size of the set s return s.size(); } // Driver Code int main() { // Given array int A[] = { 4, 5, 8, 3, 15, 5, 4, 6, 8, 10, 45 }; int N = 11; // Function Call cout << minSteps(A, N); return 0; }
Java
// JAVA program for the above approach import java.util.*; class GFG { // Function to find the // minimum number of steps required // to reduce all array elements to zero public static int minSteps(int A[], int N) { // To store all distinct array elements HashSet<Integer> s = new HashSet<>(); // Loop to iterate over the array for (int i = 0; i < N; ++i) { // If an array element is // greater than zero if (A[i] != 0) { // Insert the element // in the set s s.add(A[i]); } } // Return the size of the set s return s.size(); } // Driver Code public static void main(String[] args) { // Given array int A[] = { 4, 5, 8, 3, 15, 5, 4, 6, 8, 10, 45 }; int N = 11; // Function Call System.out.print(minSteps(A, N)); } } // This code is contributed by Taranpreet
Python3
# Python program for the above approach # Function to find the # minimum number of steps required # to reduce all array elements to zero def minSteps(A, N): # To store all distinct array elements s = set() # Loop to iterate over the array for i in range(N): # If an array element is # greater than zero if (A[i] != 0): # Insert the element # in the set s s.add(A[i]) # Return the size of the set s return len(s) # Driver Code if __name__ == '__main__': # Given array A = [ 4, 5, 8, 3, 15, 5, 4, 6, 8, 10, 45 ] N = 11 # Function Call print(minSteps(A, N)) # This code is contributed by hrithikgarg03188.
C#
// C# program for the above approach using System; using System.Collections.Generic; class GFG { // Function to find the // minimum number of steps required // to reduce all array elements to zero static int minSteps(int[] A, int N) { // To store all distinct array elements Dictionary<int, int> s = new Dictionary<int, int>(); // Loop to iterate over the array for (int i = 0; i < N; ++i) { // If an array element is // greater than zero if (A[i] != 0) { // Insert the element // in the set s if (s.ContainsKey(A[i])) { s[A[i]] = 1; } else { s.Add(A[i], 1); } } } // Return the size of the set s return s.Count; } // Driver Code public static void Main() { // Given array int[] A = { 4, 5, 8, 3, 15, 5, 4, 6, 8, 10, 45 }; int N = 11; // Function Call Console.Write(minSteps(A, N)); } } // This code is contributed by Samim Hossain Mondal.
Javascript
<script> // JavaScript program for the above approach // Function to find the // minimum number of steps required // to reduce all array elements to zero const minSteps = (A, N) => { // To store all distinct array elements let s = new Set(); // Loop to iterate over the array for (let i = 0; i < N; ++i) { // If an array element is // greater than zero if (A[i] != 0) { // Insert the element // in the set s s.add(A[i]); } } // Return the size of the set s return s.size; } // Driver Code // Given array let A = [4, 5, 8, 3, 15, 5, 4, 6, 8, 10, 45]; let N = 11; // Function Call document.write(minSteps(A, N)); // This code is contributed by rakeshsahni </script>
8
Complejidad temporal: O(N)
Espacio auxiliar: O(N)
Tema relacionado: Subarrays, subsecuencias y subconjuntos en array
Publicación traducida automáticamente
Artículo escrito por anusha00466 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA