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:
- 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}.
- 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}.
- 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}.
- 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:
- 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.
- 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++
// 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
// 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
# 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#
// 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
Javascript
<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)
Publicación traducida automáticamente
Artículo escrito por vandanakillari54935 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA