Dada una array de tamaño N , la tarea es imprimir el valor final de la array que queda en la array cuando el máximo y el segundo elemento máximo de la array se reemplazan por su diferencia absoluta en la array, repetidamente.
Nota: si los dos elementos máximos son iguales, ambos se eliminan de la array, sin reemplazar ningún valor.
Ejemplos:
Entrada: arr = [2, 7, 4, 1, 8, 1]
Salida: 1
Explicaciones:
Fusión de 7 y 8: diferencia absoluta = 7 – 8 = 1. Entonces, la array se convirtió en [2, 4, 1, 1, 1].
Fusionando 2 y 4: diferencia absoluta = 4 – 2 = 2. Entonces la array se convirtió en [2, 1, 1, 1].
Fusionando 2 y 1: diferencia absoluta = 2 – 1 = 1. Entonces la array se convirtió en [1, 1, 1].
Fusionando 1 y 1: diferencia absoluta = 4 – 2 = 0. Por lo tanto, no se fusionará nada.
Entonces array final = [1].Entrada: arr = [7, 10, 5, 4, 11, 25]
Salida: 2
Enfoque eficiente: uso de la cola de prioridad
- Cree una cola de prioridad (pila máxima binaria) que organice automáticamente el elemento en orden ordenado.
- Luego elija el primer elemento (que es máximo) y el segundo elemento (2do máximo), si ambos son iguales, no presione nada, si no es igual, presione la diferencia absoluta de ambos en la cola.
- Realice los pasos anteriores hasta que el tamaño de la cola sea igual a 1, luego devuelva el último elemento. Si la cola se vacía antes de alcanzar el tamaño 1, devuelve 0.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program to find the array value
// by repeatedly replacing max 2 elements
// with their absolute difference
#include <bits/stdc++.h>
using namespace std;
// function that return last
// value of array
int lastElement(vector<int>& arr)
{
// Build a binary max_heap.
priority_queue<int> pq;
for (int i = 0; i < arr.size(); i++) {
pq.push(arr[i]);
}
// For max 2 elements
int m1, m2;
// Iterate until queue is not empty
while (!pq.empty()) {
// if only 1 element is left
if (pq.size() == 1)
// return the last
// remaining value
return pq.top();
m1 = pq.top();
pq.pop();
m2 = pq.top();
pq.pop();
// check that difference
// is non zero
if (m1 != m2)
pq.push(m1 - m2);
}
// finally return 0
return 0;
}
// Driver Code
int main()
{
vector<int> arr = { 2, 7, 4, 1, 8, 1, 1 };
cout << lastElement(arr) << endl;
return 0;
}
// This code is contributed by shinjanpatra
C
// C++ program to find the array value
// by repeatedly replacing max 2 elements
// with their absolute difference
#include <bits/stdc++.h>
using namespace std;
// function that return last
// value of array
int lastElement(vector<int>& arr)
{
// Build a binary max_heap.
priority_queue<int> pq;
for (int i = 0; i < arr.size(); i++) {
pq.push(arr[i]);
}
// For max 2 elements
int m1, m2;
// Iterate until queue is not empty
while (!pq.empty()) {
// if only 1 element is left
if (pq.size() == 1)
// return the last
// remaining value
return pq.top();
m1 = pq.top();
pq.pop();
m2 = pq.top();
pq.pop();
// check that difference
// is non zero
if (m1 != m2)
pq.push(m1 - m2);
}
// finally return 0
return 0;
}
// Driver Code
int main()
{
vector<int> arr = { 2, 7, 4, 1, 8, 1, 1 };
cout << lastElement(arr) << endl;
return 0;
}
Java
// Java program to find the array value
// by repeatedly replacing max 2 elements
// with their absolute difference
import java.util.*;
class GFG{
// Function that return last
// value of array
static int lastElement(int[] arr)
{
// Build a binary max_heap
PriorityQueue<Integer> pq = new PriorityQueue<>(
(a, b) -> b - a);
for(int i = 0; i < arr.length; i++)
pq.add(arr[i]);
// For max 2 elements
int m1, m2;
// Iterate until queue is not empty
while(!pq.isEmpty())
{
// If only 1 element is left
if (pq.size() == 1)
{
// Return the last
// remaining value
return pq.poll();
}
m1 = pq.poll();
m2 = pq.poll();
// Check that difference
// is non zero
if (m1 != m2)
pq.add(m1 - m2);
}
// Finally return 0
return 0;
}
// Driver code
public static void main(String[] args)
{
int[] arr = new int[]{2, 7, 4, 1, 8, 1, 1 };
System.out.println(lastElement(arr));
}
}
// This code is contributed by dadi madhav
Python3
# Python3 program to find the array value # by repeatedly replacing max 2 elements # with their absolute difference from queue import PriorityQueue # Function that return last # value of array def lastElement(arr): # Build a binary max_heap. pq = PriorityQueue() for i in range(len(arr)): # Multiplying by -1 for # max heap pq.put(-1 * arr[i]) # For max 2 elements m1 = 0 m2 = 0 # Iterate until queue is not empty while not pq.empty(): # If only 1 element is left if pq.qsize() == 1: # Return the last # remaining value return -1 * pq.get() else: m1 = -1 * pq.get() m2 = -1 * pq.get() # Check that difference # is non zero if m1 != m2 : pq.put(-1 * abs(m1 - m2)) return 0 # Driver Code arr = [ 2, 7, 4, 1, 8, 1, 1 ] print(lastElement(arr)) # This code is contributed by ishayadav181
C#
// C# program to find the array value
// by repeatedly replacing max 2 elements
// with their absolute difference
using System;
using System.Collections.Generic;
class GFG{
// Function that return last
// value of array
static int lastElement(int[] arr)
{
// Build a binary max_heap
Queue<int> pq = new Queue<int>();
for(int i = 0; i < arr.Length; i++)
pq.Enqueue(arr[i]);
// For max 2 elements
int m1, m2;
// Iterate until queue is not empty
while (pq.Contains(0))
{
// If only 1 element is left
if (pq.Count == 1)
{
// Return the last
// remaining value
return pq.Peek();
}
m1 = pq.Dequeue();
m2 = pq.Peek();
// Check that difference
// is non zero
if (m1 != m2)
pq.Enqueue(m1 - m2);
}
// Finally return 0
return 0;
}
// Driver Code
public static void Main(String[] args)
{
int[] arr = { 2, 7, 4, 1, 8, 1, 1 };
Console.WriteLine(lastElement(arr));
}
}
// This code is contributed by sanjoy_62
Javascript
<script>
// JavaScript program to find the array value
// by repeatedly replacing max 2 elements
// with their absolute difference
// function that return last
// value of array
function lastElement(arr) {
// Build a binary max_heap.
let pq = [];
for (let i = 0; i < arr.length; i++) {
pq.push(arr[i]);
}
// For max 2 elements
let m1, m2;
// Iterate until queue is not empty
while (pq.length) {
// if only 1 element is left
if (pq.length == 1)
// return the last
// remaining value
return pq[pq.length - 1];
pq.sort((a, b) => a - b)
m1 = pq[pq.length - 1];
pq.pop();
m2 = pq[pq.length - 1];
pq.pop();
// check that difference
// is non zero
if (m1 != m2)
pq.push(m1 - m2);
}
// finally return 0
return 0;
}
// Driver Code
let arr = [2, 7, 4, 1, 8, 1, 1];
document.write(lastElement(arr) + "<br>");
</script>
Producción:
0
Complejidad temporal: O(N)
Complejidad auxiliar: O(N)