Dada una array arr[] de tamaño N , la tarea es encontrar el último elemento restante de la array después de eliminar consecutivamente el primer elemento y el medio de la array y, alternativamente, agregar su suma y diferencia al final de la array.
Ejemplos:
Entrada: A = {2, 4, 1, 5, 7}
Salida: 5
Explicación: durante la primera iteración, elimine arr[0] y arr[2] de la array
y agregue su suma (2 + 1 = 3) a el final de la array.
Por lo tanto, arr[] = {4, 5, 7, 3}.
Nuevamente, repita el mismo proceso y elimine arr[0] y arr[2] de la array
y ahora agregue su diferencia (7 – 4) = 3.
Por lo tanto, arr[] = {5, 3, 3}.
Después de la próxima iteración, la array se convertirá en arr[] = {3, 8}.
Y finalmente después de la última iteración, arr[] = {5} que es el último valor requerido.Entrada: arr[] = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10}
Salida: 15
Enfoque: El problema dado es un problema basado en la implementación y se puede resolver siguiendo repetitivamente los pasos dados:
- Mantenga una op variable , que almacena el recuento de la operación.
- Elimine el primer elemento y el medio de la array hasta que su tamaño sea mayor que 1 y agregue la array con su suma o resta de acuerdo con el op (es decir, e si op es par, realice la suma, de lo contrario realice la resta).
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program of the above approach
#include <bits/stdc++.h>
using namespace std;
// Function to find the last element
// in array after the given operations
int lastElement(vector<int>& arr)
{
// Maintain operation count
int op = 0, x = 0;
// Loop until array has more
// than 1 element in it
while (arr.size() != 1) {
// Stores middle index
int mid = arr.size() / 2;
// For even iterations perform
// addition otherwise subtraction
if (op % 2 == 0) {
x = arr[mid] + arr[0];
arr.erase(arr.begin() + mid);
arr.erase(arr.begin());
}
else {
x = arr[mid] - arr[0];
arr.erase(arr.begin() + mid);
arr.erase(arr.begin());
}
// Append in the end
arr.push_back(x);
// Increment operation count
op += 1;
}
// Return Answer
return arr[0];
}
// Driver Code
int main()
{
vector<int> arr = { 2, 4, 1, 5, 7 };
cout << lastElement(arr);
return 0;
}
// This code is contributed by rakeshsahni
Java
// Java program of the above approach
import java.util.*;
class GFG{
// Function to find the last element
// in array after the given operations
static int lastElement(Vector<Integer> arr)
{
// Maintain operation count
int op = 0, x = 0;
// Loop until array has more
// than 1 element in it
while (arr.size() != 1) {
// Stores middle index
int mid = arr.size() / 2;
// For even iterations perform
// addition otherwise subtraction
if (op % 2 == 0) {
x = arr.get(mid) + arr.get(0);
arr.remove(mid);
arr.remove(0);
}
else {
x = arr.get(mid) - arr.get(0);
arr.remove(mid);
arr.remove(0);
}
// Append in the end
arr.add(x);
// Increment operation count
op += 1;
}
// Return Answer
return arr.get(0);
}
// Driver Code
public static void main(String[] args)
{
Integer []arr = { 2, 4, 1, 5, 7 };
Vector<Integer> v = new Vector<Integer>();
Collections.addAll(v, arr);
System.out.print(lastElement(v));
}
}
// This code is contributed by shikhasingrajput
Python3
# Python program of the above approach # Function to find the last element # in array after the given operations def lastElement(arr): # Maintain operation count op = 0 # Loop until array has more # than 1 element in it while len(arr) != 1: # Stores middle index mid = len(arr)//2 # For even iterations perform # addition otherwise subtraction if op % 2 == 0: x = arr.pop(mid) + arr.pop(0) else: x = arr.pop(mid) - arr.pop(0) # Append in the end arr.append(x) # Increment operation count op += 1 # Return Answer return arr[0] # Driver Code if __name__ == "__main__": arr = [2, 4, 1, 5, 7] print(lastElement(arr))
C#
// C# program of the above approach
using System;
using System.Collections.Generic;
public class GFG{
// Function to find the last element
// in array after the given operations
static int lastElement(List<int> arr)
{
// Maintain operation count
int op = 0, x = 0;
// Loop until array has more
// than 1 element in it
while (arr.Count != 1) {
// Stores middle index
int mid = arr.Count / 2;
// For even iterations perform
// addition otherwise subtraction
if (op % 2 == 0) {
x = arr[mid] + arr[0];
arr.RemoveAt(mid);
arr.RemoveAt(0);
}
else {
x = arr[mid] - arr[0];
arr.RemoveAt(mid);
arr.RemoveAt(0);
}
// Append in the end
arr.Add(x);
// Increment operation count
op += 1;
}
// Return Answer
return arr[0];
}
// Driver Code
public static void Main(String[] args)
{
int []arr = { 2, 4, 1, 5, 7 };
List<int> v = new List<int>(arr);
Console.Write(lastElement(v));
}
}
// This code is contributed by shikhasingrajput
Javascript
<script>
// JavaScript code for the above approach
// Function to find the last element
// in array after the given operations
function lastElement(arr) {
// Maintain operation count
let op = 0, x = 0;
// Loop until array has more
// than 1 element in it
while (arr.length != 1) {
// Stores middle index
let mid = Math.floor(arr.length / 2);
// For even iterations perform
// addition otherwise subtraction
if (op % 2 == 0) {
x = arr[mid] + arr[0];
let p1 = arr.slice(1, mid)
let p2 = arr.slice(mid + 1)
arr = [...p1.concat(p2)];
}
else {
x = arr[mid] - arr[0];
let p1 = arr.slice(1, mid)
let p2 = arr.slice(mid + 1)
arr = [...p1.concat(p2)];
}
// Append in the end
arr.push(x);
// Increment operation count
op = op + 1;
}
// Return Answer
return arr[0];
}
// Driver Code
let arr = [2, 4, 1, 5, 7];
document.write(lastElement(arr));
// This code is contributed by Potta Lokesh
</script>
5
Complejidad de Tiempo: O(N 2 )
Espacio Auxiliar: O(1)
Publicación traducida automáticamente
Artículo escrito por harshdeepmahajan88 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA