Dada una array arr[] de enteros positivos y negativos, la tarea es imprimir la array después de eliminar los elementos de array adyacentes a partir del último índice de la array.
Los elementos de la array se pueden eliminar en función de las siguientes condiciones:
- Solo es necesario comparar dos elementos adyacentes de signo opuesto.
- Se descartará el valor absoluto menor de los dos elementos adyacentes de signo contrario.
- Ambos elementos adyacentes de igual valor absoluto de signo opuesto serán descartados.
- Si la array resultante está vacía, imprima -1.
Ejemplos:
Entrada: arr[] = { 2, 7, -6, 3, 8, -5 }
Salida: 2 7 3 8
Explicación:
Después de comparar arr[4] y arr[5], arr[5] se descarta porque |8 | > |-6|.
Después de comparar arr[1] y arr[2], arr[2] se descarta porque |7| > |-6|.
Entrada: arr[] = { 2, 7, -9, 3, 8, -5 }
Salida: -9 3 8
Explicación:
Después de comparar arr[4] y arr[5], arr[5] se descarta porque |8 | > |-5|.
Después de comparar arr[1] y arr[2], arr[1] se descarta porque |7| < |-9|.
Después de comparar arr[0] y arr[2], arr[0] se descarta porque |2| < |-9|.
Enfoque:
Para resolver el problema mencionado anteriormente, siga los pasos que se detallan a continuación:
- Recorra la array de entrada dada y, si el elemento es positivo, insértelo en el vector.
- Si el elemento es negativo, busque el estado correcto de este entero recorriendo el vector final de manera inversa y compruebe si el último elemento del vector es positivo o negativo.
- Si es positivo, comprobamos cuál de ellos será descartado comparando el valor absoluto de ambos enteros.
- Si el vector está vacío o el último elemento es negativo, empujamos el elemento actual en el vector final.
- Si al comparar el absoluto de ambos enteros obtenemos el mismo valor, entonces se descarta el último elemento del vector.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ Program to maximize removals
// of adjacent array elements based
// on their absolute value
#include <bits/stdc++.h>
using namespace std;
// Function to find remaining
// array elements after removals
void removals(int arr[], int n)
{
vector<int> v;
for (int i = 0; i < n; i++) {
// If i-th element is having
// positive value (moving right)
if (arr[i] > 0)
// Push them into
// the vector
v.push_back(arr[i]);
else {
// If the last element of the vector
// is of opposite sign and is less
// than the value of current
// integer then pop that element
while (!v.empty() && (v.back() > 0)
&& v.back() < abs(arr[i]))
v.pop_back();
// Check if vector is empty or the
// last element has same sign
if (v.empty() || v.back() < 0)
v.push_back(arr[i]);
// Check if the value is same
else if (v.back() == abs(arr[i]))
v.pop_back();
}
}
// If vector is empty
if (v.size() == 0) {
cout << -1;
return;
}
// Print the final array
for (int i = 0; i < v.size(); i++) {
cout << v[i] << " ";
}
return;
}
// Driver Code
int main()
{
int arr[] = { 2, 7, -9, 3, 8, -5 };
int n = sizeof(arr) / sizeof(arr[0]);
removals(arr, n);
return 0;
}
Java
// Java Program to maximize removals
// of adjacent array elements based
// on their absolute value
import java.util.*;
class GFG{
// Function to find remaining
// array elements after removals
static void removals(int arr[], int n)
{
Vector<Integer> v = new Vector<Integer>();
for (int i = 0; i < n; i++)
{
// If i-th element is having
// positive value (moving right)
if (arr[i] > 0)
// Push them into
// the vector
v.add(arr[i]);
else
{
// If the last element of the vector
// is of opposite sign and is less
// than the value of current
// integer then pop that element
while (!v.isEmpty() && (v.lastElement() > 0) &&
v.lastElement() < Math.abs(arr[i]))
v.remove(v.size()-1);
// Check if vector is empty or the
// last element has same sign
if (v.isEmpty() || v.lastElement() < 0)
v.add(arr[i]);
// Check if the value is same
else if (v.lastElement() == Math.abs(arr[i]))
v.remove(v.size() - 1);
}
}
// If vector is empty
if (v.size() == 0)
{
System.out.print(-1);
return;
}
// Print the final array
for (int i = 0; i < v.size(); i++)
{
System.out.print(v.get(i) + " ");
}
return;
}
// Driver Code
public static void main(String[] args)
{
int arr[] = { 2, 7, -9, 3, 8, -5 };
int n = arr.length;
removals(arr, n);
}
}
// This code is contributed by 29AjayKumar
Python3
# Python3 program to maximize removals # of adjacent array elements based # on their absolute value # Function to find remaining # array elements after removals def removals(arr, n): v = [] for i in range(n): # If i-th element is having # positive value (moving right) if (arr[i] > 0): # Push them into # the vector v.append(arr[i]) else: # If the last element of the vector # is of opposite sign and is less # than the value of current # integer then pop that element while (len(v) != 0 and v[-1] > 0 and v[-1] < abs(arr[i])): v.pop() # Check if vector is empty or the # last element has same sign if (len(v) == 0 or v[-1] < 0): v.append(arr[i]) # Check if the value is same elif (v[-1] == abs(arr[i])): v.pop() # If vector is empty if (len(v) == 0): print(-1) return # Print the final array for i in range(len(v)): print(v[i], end = " ") return # Driver Code if __name__ == "__main__": arr = [ 2, 7, -9, 3, 8, -5 ] n = len(arr) removals(arr, n) # This code is contributed by chitranayal
C#
// C# program to maximize removals
// of adjacent array elements based
// on their absolute value
using System;
using System.Collections.Generic;
class GFG{
// Function to find remaining
// array elements after removals
static void removals(int []arr, int n)
{
List<int> v = new List<int>();
for(int i = 0; i < n; i++)
{
// If i-th element is having
// positive value (moving right)
if (arr[i] > 0)
// Push them into
// the vector
v.Add(arr[i]);
else
{
// If the last element of the vector
// is of opposite sign and is less
// than the value of current
// integer then pop that element
while (v.Count != 0 && (v[v.Count - 1] > 0) &&
v[v.Count - 1] < Math.Abs(arr[i]))
v.RemoveAt(v.Count - 1);
// Check if vector is empty or the
// last element has same sign
if (v.Count == 0 || v[v.Count - 1] < 0)
v.Add(arr[i]);
// Check if the value is same
else if (v[v.Count - 1] == Math.Abs(arr[i]))
v.RemoveAt(v.Count - 1);
}
}
// If vector is empty
if (v.Count == 0)
{
Console.Write(-1);
return;
}
// Print the readonly array
for(int i = 0; i < v.Count; i++)
{
Console.Write(v[i] + " ");
}
return;
}
// Driver Code
public static void Main(String[] args)
{
int []arr = { 2, 7, -9, 3, 8, -5 };
int n = arr.Length;
removals(arr, n);
}
}
// This code is contributed by 29AjayKumar
Javascript
<script>
// JavaScript Program to maximize removals
// of adjacent array elements based
// on their absolute value
// Function to find remaining
// array elements after removals
function removals(arr,n)
{
let v = [];
for (let i = 0; i < n; i++)
{
// If i-th element is having
// positive value (moving right)
if (arr[i] > 0)
// Push them into
// the vector
v.push(arr[i]);
else
{
// If the last element of the vector
// is of opposite sign and is less
// than the value of current
// integer then pop that element
while (v.length!=0 && (v[v.length-1] > 0) &&
v[v.length-1] < Math.abs(arr[i]))
v.pop();
// Check if vector is empty or the
// last element has same sign
if (v.length==0 || v[v.length-1] < 0)
v.push(arr[i]);
// Check if the value is same
else if (v[v.length-1] == Math.abs(arr[i]))
v.pop();
}
}
// If vector is empty
if (v.length == 0)
{
document.write(-1);
return;
}
// Print the final array
for (let i = 0; i < v.length; i++)
{
document.write(v[i] + " ");
}
return;
}
// Driver Code
let arr=[ 2, 7, -9, 3, 8, -5];
let n = arr.length;
removals(arr, n);
// This code is contributed by avanitrachhadiya2155
</script>
Producción:
-9 3 8
Publicación traducida automáticamente
Artículo escrito por visheshaggarwal y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA