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
Producción:
3
Complejidad temporal: O(log N)
Espacio auxiliar: O(1)