Dada una array arr[] que consta de N enteros positivos, la tarea es verificar si es posible reducir el tamaño de la array a 1 eliminando repetidamente el elemento más pequeño de un par que tenga una diferencia absoluta de 2 o 0 entre ellos. Si no es posible reducir, imprima “-1” . De lo contrario, imprima el último elemento restante en la array.
Ejemplos:
Entrada: arr[] = {2, 4, 6, 8, 0, 8}
Salida: 8
Explicación:
arr[] = {2, 4, 6, 8, 0, 8}, Quitar 0 del par (2, 0).
array[] = {2, 4, 6, 8, 8}. Retire 2 del par (2, 4).
arr[] = {4, 6, 8, 8}, quita 4 del par (4, 6).
array[] = {6, 8, 8}. Retire 6 del par (6, 8).
array[] = {8, 8}. Eliminar 8.
arr[] = {8}Entrada: arr[] = {1, 7, 3, 3}
Salida: -1
Explicación:
arr[] = {1, 7, 3, 3}. Retire 1 del par (1, 3).
array[] = {7, 3, 3}. Retire 3 del par (3, 3).
array[] = {7, 3}. No más mudanzas posibles.
Enfoque: siga los pasos a continuación para resolver el problema:
- Ordena la array dada en orden ascendente .
- Recorra la array comenzando desde el elemento más pequeño y verifique si existe algún par de elementos adyacentes que tengan una diferencia absoluta distinta de 2 o 0 o no.
- Si se encuentra que es cierto, imprima “-1” . De lo contrario, imprima el elemento más grande presente en la array , ya que será el único elemento restante de la array después de realizar las operaciones dadas.
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 last remaining
// array element after repeatedly removing
// the smallest from pairs having absolute
// difference 2 or 0
void findLastElement(int arr[], int N)
{
// Sort the given array in
// ascending order
sort(arr, arr + N);
int i = 0;
// Traverse the array
for (i = 1; i < N; i++) {
// If difference between
// adjacent elements is
// not equal to 0 or 2
if (arr[i] - arr[i - 1] != 0
&& arr[i] - arr[i - 1] != 2) {
cout << "-1" << endl;
return;
}
}
// If operations can be performed
cout << arr[N - 1] << endl;
}
// Driver Code
int main()
{
int arr[] = { 2, 4, 6, 8, 0, 8 };
int N = sizeof(arr) / sizeof(arr[0]);
findLastElement(arr, N);
return 0;
}
Java
// Java program for the above approach
import java.util.*;
class GFG
{
// Function to find the last remaining
// array element after repeatedly removing
// the smallest from pairs having absolute
// difference 2 or 0
static void findLastElement(int arr[], int N)
{
// Sort the given array in
// ascending order
Arrays.sort(arr);
int i = 0;
// Traverse the array
for (i = 1; i < N; i++) {
// If difference between
// adjacent elements is
// not equal to 0 or 2
if (arr[i] - arr[i - 1] != 0
&& arr[i] - arr[i - 1] != 2)
{
System.out.println("-1");
return;
}
}
// If operations can be performed
System.out.println( arr[N - 1]);
}
// Driver Code
public static void main(String[] args)
{
int arr[] = { 2, 4, 6, 8, 0, 8 };
int N = arr.length;
findLastElement(arr, N);
}
}
// This code is contributed by code_hunt.
Python3
# Python program for the above approach
# Function to find the last remaining
# array element after repeatedly removing
# the smallest from pairs having absolute
# difference 2 or 0
def findLastElement(arr, N):
# Sort the given array in
# ascending order
arr.sort();
i = 0;
# Traverse the array
for i in range(1, N):
# If difference between
# adjacent elements is
# not equal to 0 or 2
if (arr[i] - arr[i - 1] != 0\
and arr[i] - arr[i - 1] != 2):
print("-1");
return;
# If operations can be performed
print(arr[N - 1]);
# Driver Code
if __name__ == '__main__':
arr = [2, 4, 6, 8, 0, 8];
N = len(arr);
findLastElement(arr, N);
# This code is contributed by 29AjayKumar.
C#
// C# program for the above approach
using System;
public class GFG
{
// Function to find the last remaining
// array element after repeatedly removing
// the smallest from pairs having absolute
// difference 2 or 0
static void findLastElement(int []arr, int N)
{
// Sort the given array in
// ascending order
Array.Sort(arr);
int i = 0;
// Traverse the array
for (i = 1; i < N; i++)
{
// If difference between
// adjacent elements is
// not equal to 0 or 2
if (arr[i] - arr[i - 1] != 0
&& arr[i] - arr[i - 1] != 2)
{
Console.WriteLine("-1");
return;
}
}
// If operations can be performed
Console.WriteLine(arr[N - 1]);
}
// Driver Code
public static void Main(String[] args)
{
int []arr = { 2, 4, 6, 8, 0, 8 };
int N = arr.Length;
findLastElement(arr, N);
}
}
// This code is contributed by 29AjayKumar
Javascript
<script>
// JavaScript program for the above approach
// Function to find the last remaining
// array element after repeatedly removing
// the smallest from pairs having absolute
// difference 2 or 0
function findLastElement(arr, N)
{
// Sort the given array in
// ascending order
arr.sort();
let i = 0;
// Traverse the array
for (i = 1; i < N; i++)
{
// If difference between
// adjacent elements is
// not equal to 0 or 2
if (arr[i] - arr[i - 1] != 0
&& arr[i] - arr[i - 1] != 2)
{
document.write("-1" + "<br>");
return;
}
}
// If operations can be performed
document.write(arr[N - 1] + "<br>");
}
// Driver Code
let arr = [ 2, 4, 6, 8, 0, 8 ];
let N = arr.length;
findLastElement(arr, N);
// This code is contributed by Surbhi Tyagi.
</script>
8
Complejidad de tiempo : O (N * logN), ya que estamos usando una función de clasificación incorporada.
Espacio auxiliar : O(1), ya que no estamos utilizando ningún espacio adicional.
Publicación traducida automáticamente
Artículo escrito por shailjapriya y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA