Encuentre el último elemento restante después de la eliminación repetida de elementos indexados pares e impares alternativamente

Dado un entero positivo N , la tarea es imprimir el último elemento restante de una secuencia [1, N] después de realizar repetidamente las siguientes operaciones en el orden dado alternativamente:

1. Elimina todos los elementos indexados impares de la secuencia.
2. Elimina todos los elementos indexados pares de la secuencia.

Ejemplos:

Entrada: N = 9
Salida: 6
Explicación: 
Secuencia = {1, 2, 3, 4, 5, 6, 7, 8, 9}
Paso 1: Eliminar elementos indexados impares modifica la secuencia a {2, 4, 6, 8 }
Paso 2: Eliminar elementos indexados pares modifica la secuencia a {2, 6}
Paso 3: Eliminar elementos indexados impares modifica la secuencia a {6}
Por lo tanto, el último elemento restante es 6.

Entrada: N = 5
Salida: 2
Explicación: 
Secuencia = {1, 2, 3, 4, 5}
Paso 1: Eliminar elementos indexados impares modifica la secuencia a {2, 4}
Paso 2: Eliminar elementos indexados pares modifica la secuencia a {2}
Por lo tanto, el último elemento restante es 2.

Enfoque ingenuo: el enfoque más simple es almacenar todos los elementos del 1 al N secuencialmente en una array. Para cada operación, elimine elementos de la array y desplace los elementos restantes hacia la izquierda. Después de reducir la array a un solo elemento, imprima ese elemento restante como la respuesta requerida. 

Complejidad de tiempo: O(N ² *log N)
Espacio auxiliar: O(N)

Enfoque eficiente: el enfoque anterior se puede optimizar mediante la programación dinámica . 
La relación de recurrencia es la siguiente:

 

donde, i está en el rango [1, N]
dp[i] almacena la respuesta cuando los elementos de la array van del 1 al i.

Siga los pasos a continuación para resolver el problema:

1. Inicialice una array dp[] donde dp[i] almacena el elemento restante o la secuencia [1, i] .
2. Para la condición base de i = 1 , imprima 1 como la respuesta requerida.
3. Calcule el valor de dp[N] usando la relación de recurrencia antes mencionada y use los subproblemas ya calculados para evitar volver a calcular los subproblemas superpuestos .
4. Después de completar los pasos anteriores, imprima el valor de dp[N] como resultado.

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

// C++14 program for the above approach
#include <bits/stdc++.h>
using namespace std;
 
// Function to calculate the last
// remaining element from the sequence
int lastRemaining(int n, map<int, int> &dp)
{
     
    // If dp[n] is already calculated
    if (dp.find(n) != dp.end())
        return dp[n];
 
    // Base Case:
    if (n == 1)
        return 1;
     
    // Recursive call
    else
        dp[n] = 2 * (1 + n / 2 -
           lastRemaining(n / 2, dp));
 
    // Return the value of dp[n]
    return dp[n];
}
 
// Driver Code
int main()
{
     
    // Given N
    int N = 5;
     
    // Stores the
    map<int, int> dp;
     
    // Function call
    cout << lastRemaining(N, dp);
     
    return 0;
}
 
// This code is contributed by mohit kumar 29

// Java program for
// the above approach
import java.util.*;
class GFG{
 
// Function to calculate the last
// remaining element from the sequence
static int lastRemaining(int n, HashMap<Integer,
                                        Integer> dp)
{
  // If dp[n] is already calculated
  if (dp.containsKey(n))
    return dp.get(n);
 
  // Base Case:
  if (n == 1)
    return 1;
 
  // Recursive call
  else
    dp.put(n, 2 * (1 + n / 2 -
           lastRemaining(n / 2, dp)));
 
  // Return the value of dp[n]
  return dp.get(n);
}
 
// Driver Code
public static void main(String[] args)
{   
  // Given N
  int N = 5;
 
  // Stores the
  HashMap<Integer,
          Integer> dp = new HashMap<Integer,
                                    Integer>();
 
  // Function call
  System.out.print(lastRemaining(N, dp));
}
}
 
// This code is contributed by Princi Singh

# Python program for the above approach
 
# Function to calculate the last
# remaining element from the sequence
def lastRemaining(n, dp):
 
  # If dp[n] is already calculated
    if n in dp:
        return dp[n]
 
    # Base Case:
    if n == 1:
        return 1
 
    # Recursive Call
    else:
        dp[n] = 2*(1 + n//2
        - lastRemaining(n//2, dp))
 
    # Return the value of dp[n]
    return dp[n]
 
 
# Driver Code
 
# Given N
N = 5
 
# Stores the
dp = {}
 
# Function Call
print(lastRemaining(N, dp))

// C# program for the above approach
using System;
using System.Collections.Generic;
 
class GFG{
 
// Function to calculate the last
// remaining element from the sequence
static int lastRemaining(int n, Dictionary<int,
                                           int> dp)
{
     
    // If dp[n] is already calculated
    if (dp.ContainsKey(n))
        return dp[n];
     
    // Base Case:
    if (n == 1)
        return 1;
     
    // Recursive call
    else
        dp.Add(n, 2 * (1 + n / 2 -
             lastRemaining(n / 2, dp)));
     
    // Return the value of dp[n]
    return dp[n];
}
 
// Driver Code
public static void Main(String[] args)
{ 
     
    // Given N
    int N = 5;
     
    // Stores the
    Dictionary<int,
               int> dp = new Dictionary<int,
                                        int>();
     
    // Function call
    Console.Write(lastRemaining(N, dp));
}
}
 
// This code is contributed by Princi Singh

<script>
      // JavaScript program for the above approach
      // Function to calculate the last
      // remaining element from the sequence
      function lastRemaining(n, dp) {
        // If dp[n] is already calculated
        if (dp.hasOwnProperty(n))
            return dp[n];
 
        // Base Case:
        if (n === 1)
            return 1;
        // Recursive call
        else
          dp[n] =
            2 * (1 + parseInt(n / 2) -
            lastRemaining(parseInt(n / 2), dp));
 
        // Return the value of dp[n]
        return dp[n];
      }
 
      // Driver Code
      // Given N
      var N = 5;
 
      // Stores the
      var dp = {};
 
      // Function call
      document.write(lastRemaining(N, dp));
</script>

2

Complejidad de tiempo : O (N), ya que estamos usando un bucle para atravesar N veces.

Espacio auxiliar : O(N), ya que estamos usando espacio extra para dp.