Dada una array de enteros arr[] , la tarea es encontrar el elemento restante en la array después de realizar las siguientes operaciones:
- En cada turno, elija los dos enteros máximos X e Y de la array.
- Si X == Y, elimine ambos elementos de la array.
- Si X != Y, inserte un elemento en la array igual a abs(X – Y) .
Nota: Si no queda ningún elemento, imprima 0.
Ejemplos:
Entrada: arr[] = [3, 4, 6, 2, 7, 1]
Salida: 1
Explicación:
Los elementos 7 y 6 se reducen a 1, por lo que la array se convierte en [3, 4, 2, 1, 1]
Elementos 3 y 4 se reducen a 2, por lo que la array se convierte en [2, 1, 1, 1]
Los elementos 2 y 1 se reducen a 1, por lo que la array se convierte en [1, 1, 1] El
elemento 1 es completamente destruido por otro 1, por lo que la array es [1] al final.
Entrada: arr[] = [1, 2, 3, 4, 5]
Salida: 1
Explicación:
Los elementos 4 y 5 se reducen a 1, por lo que la array se convierte en [1, 2, 3, 1] Los
elementos 2 y 3 se reducen a 1, por lo que la array se convierte en [1, 1, 1]
El elemento 1 es completamente destruido por otro 1, por lo que la array es [1] al final.
Enfoque:
para resolver el problema mencionado anteriormente, necesitamos usar Heap Data Structure . Los montones se usan porque solo requerimos el elemento máximo actual para cada instante y no nos preocupamos por el resto de los elementos.
- Cree un Max Heap a partir de los elementos de la array dada.
- Siga extrayendo el elemento superior dos veces por cada iteración. Si su diferencia absoluta es distinta de cero, devuelva su diferencia a la cola.
- Continúe hasta que solo quede uno o ningún elemento.
- Si no quedan elementos, imprima 0. De lo contrario, imprima el elemento restante.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ Program to reduce the
// array to almost one element
// by the given operations
#include <bits/stdc++.h>
using namespace std;
// Function to find the remaining
// element of array
int reduceArray(vector<int>& arr)
{
priority_queue<int> p;
// Build a priority queue
// using the array
for (int i = 0; i < arr.size(); ++i)
p.push(arr[i]);
// Continue until the priority
// queue has one or no elements
// remaining
while (p.size() > 1) {
// Top-most integer from heap
int y = p.top();
p.pop();
// Second integer from heap
int x = p.top();
p.pop();
// Resultant value
int val = y - x;
if (val != 0)
p.push(val);
}
// Return 0 if no elements are left
if (p.size() == 0)
return 0;
// Return top value of the heap
return p.top();
}
// Driver code
int main()
{
vector<int> arr
= { 3, 4, 6, 2, 7, 1 };
cout << reduceArray(arr)
<< "\n";
return 0;
}
Java
// Java program to reduce the
// array to almost one element
// by the given operations
import java.util.*;
class GFG{
// Function to find the remaining
// element of array
static int reduceArray(int[] arr)
{
PriorityQueue<Integer> p = new PriorityQueue<>(
11, Collections.reverseOrder());
// Build a priority queue
// using the array
for(int i = 0; i < arr.length; ++i)
p.add(arr[i]);
// Continue until the priority
// queue has one or no elements
// remaining
while (p.size() > 1)
{
// Top-most integer from heap
int y = p.poll();
// Second integer from heap
int x = p.poll();
// Resultant value
int val = y - x;
if (val != 0)
p.add(val);
}
// Return 0 if no elements are left
if (p.size() == 0)
return 0;
// Return top value of the heap
return p.poll();
}
// Driver code
public static void main(String[] args)
{
int arr[] = { 3, 4, 6, 2, 7, 1 };
System.out.println(reduceArray(arr));
}
}
// This code is contributed by jrishabh99
Python3
# Python3 program to reduce the # array to almost one element # by the given operations # Function to find the remaining # element of array import heapq def reduceArray(arr): # Build a max heap by heapq module # using the array heapq._heapify_max(arr) # Continue until the priority # queue has one or no elements # remaining while len(arr) > 1: # extracting maximum element of the max # heap into x x = arr[0] # assigning last element of the heap to # root element of the heap arr[0] = arr[-1] # reducing max heap size by 1 arr = arr[:-1] # again calling heapify to maintain # max heap property heapq._heapify_max(arr) # now extracting maximum element of the max # heap into y y = arr[0] # assigning last element of the heap to # root element of the heap arr[0] = arr[-1] # reducing max heap size by 1 arr = arr[:-1] # finding absolute difference of x and y val = abs(x-y) # if both x and y are not equal, then # inserting their absolute difference # back into the heap if val != 0: arr.append(val) # agian maintaining the max heap # with the help of heapify() heapq._heapify_max(arr) if len(arr) == 0: return 0 return arr[0] # Driver Code arr = [3, 4, 6, 2, 7, 1] print(reduceArray(arr)) '''Code is contributed by Rajat Kumar (GLAU)
Javascript
<script>
// JavaScript program to reduce the
// array to almost one element
// by the given operations
// Function to find the remaining
// element of array
function reduceArray(arr){
let p = []
// Build a priority queue
// using the array
for(let i = 0; i < arr.length; i++)
p.push(arr[i])
p.sort().reverse()
// Continue until the priority
// queue has one or no elements
// remaining
while (p.length > 1){
// Top-most integer from heap
let y = p[0]
p.splice(0,1)
// Second integer from heap
let x = p[0]
p.splice(0,1)
// Resultant value
let val = y - x
if (val != 0)
p.push(val)
p.sort().reverse()
}
// Return 0 if no elements are left
if (p.length == 0)
return 0
// Return top value of the heap
return p[0]
}
// Driver code
let arr = [ 3, 4, 6, 2, 7, 1 ]
document.write(reduceArray(arr),"</br>")
// This code is contributed by Shinjanpatra
</script>
1
Complejidad de tiempo: O (NlogN)