Encuentre el último elemento restante después de la eliminación repetida de un elemento de pares de elementos de array adyacentes crecientes

Dada una array arr[] que consta de N enteros, la tarea es imprimir el último elemento restante de la array después de seleccionar repetidamente pares de elementos adyacentes crecientes (arr[i], arr[i + 1]) y eliminar cualquiera de los elementos de la array. par. Si no es posible reducir la array a un solo elemento, imprima «No es posible» .

Ejemplos:

Entrada: arr[] = {3, 1, 2, 4}
Salida: 4
Explicación:
Paso 1: Elija un par (1, 2) y elimine 2 de él. Ahora la array se convierte en [3, 1, 4].
Paso 2: Elija el par (1, 4) y elimine 1 de él. Ahora la array se convierte en [3, 4].
Paso 3: elige el par (3, 4) y quita 3 de él. Ahora la array se convierte en [4].
Por lo tanto, el elemento restante es 4.

Entrada: arr[] = {2, 3, 1}
Salida: No es posible

Enfoque: el problema dado se puede resolver observando el hecho de que si el primer elemento de la array es menor que el último elemento de la array, entonces todos los elementos entre ellos se pueden eliminar realizando las operaciones dadas. Por lo tanto, simplemente verifique si arr[0] < arr[N – 1] o no. Si se encuentra que es cierto, imprima el primer o el último elemento de la array. De lo contrario, imprima -1 .

A continuación se muestra la implementación del enfoque anterior:

// C++ program for the above approach
#include <bits/stdc++.h>
using namespace std;
 
// Function to print the last remaining
// array element after after performing
// given operations
void canArrayBeReduced(int arr[], int N)
{
    // If size of the array is 1
    if (N == 1) {
        cout << arr[0];
        return;
    }
 
    // Check for the condition
    if (arr[0] < arr[N - 1]) {
        cout << arr[N - 1];
    }
 
    // If condition is not satisfied
    else
        cout << "Not Possible";
}
 
// Driver Code
int main()
{
    int arr[] = { 6, 5, 2, 4, 1, 3, 7 };
    int N = sizeof(arr) / sizeof(arr[0]);
 
    // Function Call
    canArrayBeReduced(arr, N);
 
    return 0;
}

// Java program for the above approach
import java.io.*;
class GFG
{
 
  // Function to print the last remaining
  // array element after after performing
  // given operations
  static void canArrayBeReduced(int[] arr, int N)
  {
 
    // If size of the array is 1
    if (N == 1)
    {
      System.out.print(arr[0]);
      return;
    }
 
    // Check for the condition
    if (arr[0] < arr[N - 1])
    {
      System.out.print(arr[N - 1]);
    }
 
    // If condition is not satisfied
    else
      System.out.print("Not Possible");
  }
 
  // Driver Code
  public static void main(String[] args)
  {
    int[] arr = { 6, 5, 2, 4, 1, 3, 7 };
    int N = arr.length;
 
    // Function Call
    canArrayBeReduced(arr, N);
  }
}
 
// This code is contributed by Dharanendra L V.

# Python 3 program for the above approach
 
# Function to print the last remaining
# array element after after performing
# given operations
def canArrayBeReduced(arr,  N):
 
    # If size of the array is 1
    if (N == 1):
        print(arr[0])
        return
 
    # Check for the condition
    if (arr[0] < arr[N - 1]):
        print(arr[N - 1])
 
    # If condition is not satisfied
    else:
        print("Not Possible")
 
 
# Driver Code
if __name__ == "__main__":
 
    arr = [6, 5, 2, 4, 1, 3, 7]
    N = len(arr)
 
    # Function Call
    canArrayBeReduced(arr, N)
 
    # This code is contributed by chitranayal.

// C# program for the above approach
using System;
 
public class GFG {
 
  // Function to print the last remaining
  // array element after after performing
  // given operations
  static void canArrayBeReduced(int[] arr, int N)
  {
 
    // If size of the array is 1
    if (N == 1)
    {
      Console.Write(arr[0]);
      return;
    }
 
    // Check for the condition
    if (arr[0] < arr[N - 1])
    {
      Console.Write(arr[N - 1]);
    }
 
    // If condition is not satisfied
    else
      Console.Write("Not Possible");
  }
 
  // Driver Code
  static public void Main()
  {
    int[] arr = { 6, 5, 2, 4, 1, 3, 7 };
    int N = arr.Length;
 
    // Function Call
    canArrayBeReduced(arr, N);
  }
}
 
// This code is contributed by Dharanendra L V.

<script>
// JavaScript program for the above approach
 
// Function to print the last remaining
// array element after after performing
// given operations
function canArrayBeReduced(arr, N)
{
 
    // If size of the array is 1
    if (N == 1)
    {
        document.write(arr[0]);
        return;
    }
 
    // Check for the condition
    if (arr[0] < arr[N - 1])
    {
        document.write(arr[N - 1]);
    }
 
    // If condition is not satisfied
    else
        document.write("Not Possible");
}
 
// Driver Code
 
    let arr = [ 6, 5, 2, 4, 1, 3, 7 ];
    let N = arr.length;
 
    // Function Call
    canArrayBeReduced(arr, N);
 
// This code is contributed by Surbhi Tyagi.
</script>

7

Complejidad de tiempo : O(1), ya que no estamos usando bucles ni recursividad.

Espacio auxiliar : O(1), ya que no estamos utilizando ningún espacio adicional.