Dada una array arr[] que consta de N enteros, la tarea es encontrar el último elemento restante de la array después de eliminar cada segundo elemento, comenzando por el primero y el último alternativamente.
Ejemplos:
Entrada: arr[] = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10}
Salida: 8
Explicación: Los elementos de la lista son: 1 2 3 4 5 6 7 8 9 10
A partir de primer elemento de array, eliminando cada segundo elemento de arr[] = { 1, 2. 3, 4, 5 , 6, 7, 8, 9, 10} modifica arr[] a {2, 4, 6, 8, 10} .
Comenzando desde el último elemento de la array, eliminando cada segundo elemento de arr[] = { 2, 4, 6 , 8, 10 } modifica arr[] a {4, 8}.
A partir de la primeraelemento de array, eliminando cada segundo elemento de arr[] = { 4, 8} modifica arr[] a {8}.
Por lo tanto, el último elemento que queda en la array es 8.Entrada: arr[] = {2, 3, 5, 6}
Salida: 3
Enfoque ingenuo: el enfoque más simple para resolver este problema es eliminar cada segundo elemento de la array, comenzando por el primer y el último índice alternativamente hasta que el tamaño de la array se reduzca a 1 . Imprime el último elemento de la array que queda después de realizar las operaciones dadas.
Complejidad de Tiempo: O(N 2 )
Espacio Auxiliar: O(1)
Enfoque eficiente: el enfoque anterior también se puede optimizar mediante una observación en la siguiente ilustración para N = 20 :
De la ilustración anterior se pueden hacer las siguientes observaciones:
- Cada vez que se eliminan N/2 números.
- Si la dirección de giro es de izquierda a derecha (→), el primer elemento de la secuencia cambia a (currentFirstElement + 2 step – 1 ) .
- Si la dirección de giro es de derecha a izquierda (←) y luego los números restantes en la lista son impares , el primer elemento de la secuencia cambia a (currentFirstElement + 2 step – 1 ) .
- Después de obtener el valor final de currentFirstElement de los pasos anteriores, imprima el valor como el elemento restante en la secuencia.
Pasos:
- Inicialice una variable, digamos leftTurn , para verificar si el elemento se eliminará desde la izquierda o la derecha.
- Inicialice las variables stayElements como N , steps como 1 y head como 1 , para almacenar el elemento restante en la secuencia, una cantidad de pasos realizados y el primer elemento de la secuencia.
- Iterar hasta que los elementos restantes sean mayores que 1 :
- si el valor de giro a la izquierda es verdadero , actualice la cabeza como (cabeza + 2 pasos – 1 ) . De lo contrario, si el elemento restante es impar, actualice la cabeza como (cabeza + 2 pasos – 1 ) .
- Actualice el valor de stayElement como stayElement/2 .
- Actualice los pasos como 2 * pasos .
- Alternar a la izquierda Gire para eliminar elementos de la derecha.
- Después de completar los pasos anteriores, imprima el valor en el índice (cabeza – 1) como el elemento restante.
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 // remaining in the array after // performing the given operations void printLastElement(int arr[], int N) { // Checks if traversal is from // left to right or vice versa bool leftTurn = true; // Store the elements currently // present in the array int remainElements = N; // Store the distance between 2 // consecutive array elements int step = 1; // Store the first element // of the remaining array int head = 1; // Iterate while elements // are greater than 1 while (remainElements > 1) { // If left to right turn if (leftTurn) { // Update head head = head + step; } // Otherwise, check if the // remaining elements are odd else { // If true, update head if (remainElements % 2 == 1) head = head + step; } // Eliminate half of the array elements remainElements = remainElements / 2; // Double the steps after each turn step = step * 2; // Alter the turn leftTurn = !leftTurn; } // Print the remaining element cout << arr[head - 1]; } // Driver Code int main() { int arr[] = { 2, 3, 5, 6 }; int N = sizeof(arr) / sizeof(arr[0]); printLastElement(arr, N); return 0; }
Java
// Java program for the above approach import java.lang.*; class GFG{ // Function to find the last element // remaining in the array after // performing the given operations public static void printLastElement(int arr[], int N) { // Checks if traversal is from // left to right or vice versa boolean leftTurn = true; // Store the elements currently // present in the array int remainElements = N; // Store the distance between 2 // consecutive array elements int step = 1; // Store the first element // of the remaining array int head = 1; // Iterate while elements // are greater than 1 while (remainElements > 1) { // If left to right turn if (leftTurn) { // Update head head = head + step; } // Otherwise, check if the // remaining elements are odd else { // If true, update head if (remainElements % 2 == 1) head = head + step; } // Eliminate half of the array elements remainElements = remainElements / 2; // Double the steps after each turn step = step * 2; // Alter the turn leftTurn = !leftTurn; } // Print the remaining element System.out.print( arr[head - 1]); } // Driver code public static void main(String args[]) { int[] arr = { 2, 3, 5, 6 }; int N = arr.length; printLastElement(arr, N); } } // This code is contributed by SoumikMondal
Python3
# Python3 program for the above approach # Function to find the last element # remaining in the array after # performing the given operations def printLastElement(arr, N): # Checks if traversal is from # left to right or vice versa leftTurn = True # Store the elements currently # present in the array remainElements = N # Store the distance between 2 # consecutive array elements step = 1 # Store the first element # of the remaining array head = 1 # Iterate while elements # are greater than 1 while (remainElements > 1): # If left to right turn if (leftTurn): # Update head head = head + step # Otherwise, check if the # remaining elements are odd else: # If true, update head if (remainElements % 2 == 1): head = head + step # Eliminate half of the array elements remainElements = remainElements // 2 # Double the steps after each turn step = step * 2 # Alter the turn leftTurn = not leftTurn # Print the remaining element print(arr[head - 1]) # Driver Code if __name__ == "__main__": arr = [ 2, 3, 5, 6 ] N = len(arr) printLastElement(arr, N) # This code is contributed by ukasp
Javascript
<script> // Javascript program for the above approach // Function to find the last element // remaining in the array after // performing the given operations function printLastElement(arr, N) { // Checks if traversal is from // left to right or vice versa var leftTurn = true; // Store the elements currently // present in the array var remainElements = N; // Store the distance between 2 // consecutive array elements var step = 1; // Store the first element // of the remaining array var head = 1; // Iterate while elements // are greater than 1 while (remainElements > 1) { // If left to right turn if (leftTurn) { // Update head head = head + step; } // Otherwise, check if the // remaining elements are odd else { // If true, update head if (remainElements % 2 == 1) head = head + step; } // Eliminate half of the array elements remainElements = remainElements / 2; // Double the steps after each turn step = step * 2; // Alter the turn leftTurn = !leftTurn; } // Print the remaining element document.write(arr[head - 1]); } // Driver code var arr = [ 2, 3, 5, 6 ]; var N = arr.length; printLastElement(arr, N); // This code is contributed by Ankita saini </script>
C#
// C# program for the above approach using System; public class GFG{ // Function to find the last element // remaining in the array after // performing the given operations public static void printLastElement(int[] arr, int N) { // Checks if traversal is from // left to right or vice versa bool leftTurn = true; // Store the elements currently // present in the array int remainElements = N; // Store the distance between 2 // consecutive array elements int step = 1; // Store the first element // of the remaining array int head = 1; // Iterate while elements // are greater than 1 while (remainElements > 1) { // If left to right turn if (leftTurn) { // Update head head = head + step; } // Otherwise, check if the // remaining elements are odd else { // If true, update head if (remainElements % 2 == 1) head = head + step; } // Eliminate half of the array elements remainElements = remainElements / 2; // Double the steps after each turn step = step * 2; // Alter the turn leftTurn = !leftTurn; } // Print the remaining element Console.Write( arr[head - 1]); } // Driver code static public void Main (){ int[] arr = { 2, 3, 5, 6 }; int N = arr.Length; printLastElement(arr, N); } } // This code is contributed by avanitrachhadiya2155
3
Complejidad temporal: O(log N)
Espacio auxiliar: O(1)