Reduzca la array dada de [1, N] girando hacia la izquierda o hacia la derecha según las condiciones dadas

Dada una array ordenada arr[] de los primeros N números naturales y un entero X , la tarea es imprimir el último elemento restante después de realizar las siguientes operaciones (N – 1) veces:

• Si el valor de X es 1 , gire a la derecha la array en 1 unidad y elimine el último elemento.
• Si el valor de X es 2 , gire a la izquierda la array en 1 unidad y elimine el primer elemento.

Ejemplos:

Entrada: N = 5, arr[] = {1, 2, 3, 4, 5}, X = 1
Salida: 3
Explicación:
Las operaciones se realizan de la siguiente manera:

1. Girar la array 1 unidad a la derecha modifica la array a {5, 1, 2, 3, 4}. Eliminar el elemento de la array modifica la array a {5, 1, 2, 3}.
2. Girar la array 1 unidad a la derecha modifica la array a {3, 5, 1, 2}. Eliminar el elemento de la array modifica la array a {3, 5, 1}.
3. Girar la array 1 unidad a la derecha modifica la array a {1, 3, 5}. Eliminar el elemento de la array modifica la array a {1, 3}.
4. Girar la array 1 unidad a la derecha modifica la array a {3, 1}. Eliminar el elemento de la array modifica la array a {3}.

Por lo tanto, el último elemento restante es 3.

Entrada: N = 5, arr[] = {1, 2, 3, 4, 5}, X = 2
Salida: 3

Enfoque ingenuo: el enfoque más simple para resolver el problema dado es empujar todos los números del rango [1, N] en un deque y realizar las operaciones dadas (N – 1) veces de acuerdo con el valor dado de X y luego imprimir el último elemento restante.

Complejidad temporal: O(N)
Espacio auxiliar: O(1)

Enfoque eficiente: el problema dado se puede optimizar en función de las siguientes observaciones: 

1. Si el valor de X es 1 , entonces el último elemento de la izquierda será la diferencia entre la potencia más pequeña de 2 N mayor y N.
2. Si el valor de X es 2 , entonces el último elemento de la izquierda será 2*(N – D) + 1, donde D representa la mayor potencia de 2 menor o igual que N.

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

• Almacene la potencia de 2 mayor que N en una variable, digamos nextPower.
• Si el valor de X es 1 , imprima el valor (nextPower – N) como resultado.
• De lo contrario, imprima el valor 2*(N – nextPower / 2) + 1 como resultado.

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 find the last element
// left after performing N - 1 queries
// of type X
int rotate(int arr[], int N, int X)
{
    // Stores the next power of 2
    long long int nextPower = 1;
 
    // Iterate until nextPower is at most N
    while (nextPower <= N)
        nextPower *= 2;
 
    // If X is equal to 1
    if (X == 1)
        return nextPower - N;
 
    // Stores the power of 2 less than or
    // equal to N
    long long int prevPower = nextPower / 2;
 
    // Return the final value
    return 2 * (N - prevPower) + 1;
}
 
// Driver Code
int main()
{
    int arr[] = { 1, 2, 3, 4, 5 };
    int X = 1;
    int N = sizeof(arr) / sizeof(arr[0]);
 
    cout << rotate(arr, N, X);
 
    return 0;
}

// Java program for the above approach
import java.io.*;
 
class GFG
{
   
  // Function to find the last element
// left after performing N - 1 queries
// of type X
static int rotate(int arr[], int N, int X)
{
   
    // Stores the next power of 2
    long nextPower = 1;
 
    // Iterate until nextPower is at most N
    while (nextPower <= N)
        nextPower *= 2;
 
    // If X is equal to 1
    if (X == 1)
        return (int) nextPower - N;
 
    // Stores the power of 2 less than or
    // equal to N
    long prevPower = nextPower / 2;
 
    // Return the final value
    return 2 * (N - (int)prevPower) + 1;
}
 
// Driver Code
    public static void main (String[] args) {
        int arr[] = { 1, 2, 3, 4, 5 };
    int X = 1;
    int N =arr.length;
 
   System.out.println(rotate(arr, N, X));
 
    }
}
 
    // This code is contributed by Potta Lokesh

# Python3 program for the above approach
 
# Function to find the last element
# left after performing N - 1 queries
# of type X
def rotate(arr, N, X):
    # Stores the next power of 2
    nextPower = 1
 
    # Iterate until nextPower is at most N
    while (nextPower <= N):
        nextPower *= 2
 
    # If X is equal to 1
    if (X == 1):
        ans = nextPower - N
        return ans
 
    # Stores the power of 2 less than or
    # equal to N
    prevPower = nextPower // 2
 
    # Return the final value
    return 2 * (N - prevPower) + 1
 
 
# Driver Code
arr = [1, 2, 3, 4, 5]
X = 1
N = len(arr)
print(rotate(arr, N, X))
 
# This code is contributed by amreshkumar3.

// C# program for the above approach
using System;
using System.Collections.Generic;
 
class GFG{
 
// Function to find the last element
// left after performing N - 1 queries
// of type X
static int rotate(int []arr, int N, int X)
{
     
    // Stores the next power of 2
    int nextPower = 1;
 
    // Iterate until nextPower is at most N
    while (nextPower <= N)
        nextPower *= 2;
 
    // If X is equal to 1
    if (X == 1)
        return nextPower - N;
 
    // Stores the power of 2 less than or
    // equal to N
    int prevPower = nextPower / 2;
 
    // Return the final value
    return 2 * (N - prevPower) + 1;
}
 
// Driver Code
public static void Main()
{
    int []arr = { 1, 2, 3, 4, 5 };
    int X = 1;
    int N = arr.Length;
 
    Console.Write(rotate(arr, N, X));
}
}
 
// This code is contributed by SURENDRA_GANGWAR

<script>
       // JavaScript program for the above approach
 
       // Function to find the last element
       // left after performing N - 1 queries
       // of type X
       function rotate(arr, N, X) {
           // Stores the next power of 2
           let nextPower = 1;
 
           // Iterate until nextPower is at most N
           while (nextPower <= N)
               nextPower *= 2;
 
           // If X is equal to 1
           if (X == 1)
               return nextPower - N;
 
           // Stores the power of 2 less than or
           // equal to N
           let prevPower = nextPower / 2;
 
           // Return the final value
           return 2 * (N - prevPower) + 1;
       }
 
       // Driver Code
       let arr = [1, 2, 3, 4, 5];
       let X = 1;
       let N = arr.length;
 
       document.write(rotate(arr, N, X));
 
   // This code is contributed by Potta Lokesh
 
   </script>

3

Complejidad temporal: O(log N)
Espacio auxiliar: O(1)