Encuentre el último elemento restante después de reducir la array

Dada una array arr[] de tamaño N y un entero K . La tarea es encontrar el último elemento que queda en la array después de reducir la array. Las reglas para reducir la array son: 
 

• El primer y último elemento dicen que X e Y se eligen y eliminan de la array arr[].
• Se suman los valores X e Y. Z = X + Y.
• Inserte el valor de Z % K en la array arr[] en la posición ((N/2) + 1) ^ésima posición, donde N denota la longitud actual de la array.

Ejemplos: 
 

Entrada: N = 5, arr[] = {1, 2, 3, 4, 5}, K = 7 
Salida: 1 
Explicación: 
La array dada arr[] se reduce de la siguiente manera: 
{1, 2, 3, 4, 5 } -> {2, 6, 3, 4} 
{2, 6, 3, 4} -> {6, 6, 3} 
{6, 6, 3} -> {2, 6} 
{2, 6} – > {1} 
El último elemento de A es 1.
Entrada: N = 5, arr[] = {2, 4, 7, 11, 3}, K = 12 
Salida: 3 
Explicación: 
La array dada arr[] se reduce como sigue: 
{2, 4, 7, 11, 3} -> {4, 5, 7, 11} 
{4, 5, 7, 11} -> {5, 3, 7} 
{5, 3, 7} – > {0, 3} 
{0, 3} -> {3} 
El último elemento de A es 3. 
 

Enfoque ingenuo: el enfoque ingenuo para este problema es que en cada paso, encuentre el primer elemento y el último elemento en la array y calcule (X + Y) % K donde X es el primer elemento e Y es el último elemento de la array en cada paso. Después de calcular este valor, inserte este valor en la posición dada. 
Complejidad de tiempo: O(N ² )
Enfoque eficiente: 
 

• Observando detenidamente, se puede decir que la suma de los elementos del arreglo módulo K nunca cambia en todo el arreglo.
• Esto se debe a que básicamente estamos insertando el valor X + Y % K nuevamente en la array.
• Por lo tanto, este problema se puede resolver en tiempo lineal al encontrar directamente la suma de la array y encontrar el valor sum % K .

A continuación se muestra la implementación del enfoque anterior:
 

// C++ program to find the value of the
// reduced Array by reducing the array
// based on the given conditions
 
#include <iostream>
using namespace std;
 
// Function to find the value of the
// reduced Array by reducing the array
// based on the given conditions
int find_value(int a[], int n, int k)
{
    // Variable to store the sum
    int sum = 0;
 
    // For loop to iterate through the
    // given array and find the sum
    for (int i = 0; i < n; i++) {
        sum += a[i];
    }
 
    // Return the required value
    return sum % k;
}
 
// Driver code
int main()
{
    int n = 5, k = 3;
    int a[] = { 12, 4, 13, 0, 5 };
    cout << find_value(a, n, k);
    return 0;
}

// Java program to find the value of the
// reduced Array by reducing the array
// based on the given conditions
 
public class GFG {
 
    // Function to find the value of the
    // reduced Array by reducing the array
    // based on the given conditions
    public static int find_value(int a[], int n, int k)
    {
        // Variable to store the sum
        int sum = 0;
 
        // For loop to iterate through the
        // given array and find the sum
        for (int i = 0; i < n; i++) {
            sum += a[i];
        }
 
        // Return the required value
        return sum % k;
    }
 
    // Driver code
    public static void main(String[] args)
    {
        int n = 5, k = 3;
        int a[] = { 12, 4, 13, 0, 5 };
        System.out.println(find_value(a, n, k));
    }
}

# Python3 program to find the value of the
# reduced Array by reducing the array
# based on the given conditions
 
# Function to find the value of the
# reduced Array by reducing the array
# based on the given conditions
def find_value(a, n, k):
 
    # Variable to store the sum
    sum = 0
 
    # For loop to iterate through the
    # given array and find the sum
    for i in range(n):
        sum += a[i]
 
    # Return the required value
    return sum % k
 
# Driver code
if __name__ == "__main__":
    n, k = 5, 3;
    a = [12, 4, 13, 0, 5];
    print(find_value(a, n, k))

// C# program to find the value of the
// reduced Array by reducing the array
// based on the given conditions
using System;
 
class GFG {
 
    // Function to find the value of the
    // reduced Array by reducing the array
    // based on the given conditions
    public static int find_value(int []a, int n, int k)
    {
        // Variable to store the sum
        int sum = 0;
 
        // For loop to iterate through the
        // given array and find the sum
        for (int i = 0; i < n; i++) {
            sum += a[i];
        }
 
        // Return the required value
        return sum % k;
    }
 
    // Driver code
    public static void Main(string[] args)
    {
        int n = 5, k = 3;
        int []a = { 12, 4, 13, 0, 5 };
        Console.WriteLine(find_value(a, n, k));
    }
}
 
// This code is contributed  by AnkitRai01

<script>
 
 
// Js program to find the value of the
// reduced Array by reducing the array
// based on the given conditions
 
// Function to find the value of the
// reduced Array by reducing the array
// based on the given conditions
function find_value( a, n, k)
{
    // Variable to store the sum
    let sum = 0;
 
    // For loop to iterate through the
    // given array and find the sum
    for (let i = 0; i < n; i++) {
        sum += a[i];
    }
 
    // Return the required value
    return sum % k;
}
 
// Driver code
let n = 5, k = 3;
    let a = [ 12, 4, 13, 0, 5 ];
document.write(find_value(a, n, k));
 
 
</script>

1

Complejidad de tiempo: O(N)