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