# Remaining array element after repeated removal of last element and subtraction of each element from next adjacent element

Given an array **arr[]** consisting of **N** integers, the task is to find the remaining array element after subtracting each element from its next adjacent element and removing the last array element repeatedly.

**Examples:**

Attention reader! Don’t stop learning now. Get hold of all the important DSA concepts with the **DSA Self Paced Course** at a student-friendly price and become industry ready. To complete your preparation from learning a language to DS Algo and many more, please refer **Complete Interview Preparation Course****.**

In case you wish to attend **live classes **with experts, please refer **DSA Live Classes for Working Professionals **and **Competitive Programming Live for Students**.

Input:arr[] = {3, 4, 2, 1}Output:4Explanation:

Operation 1: The array arr[] modifies to {4 – 3, 2 – 4, 1 – 2} = {1, -2, -1}.

Operation 2: The array arr[] modifies to {-2 – 1, -1 + 2} = {-3, 1}.

Operation 3: The array arr[] modifies to {1 + 3} = {4}.

Therefore, the last remaining array element is 4.

Input:arr[] = {1, 8, 4}Output:-11Explanation:

Operation 1: The array arr[] modifies to {1 – 8, 4 – 8} = {7, -4}.

Operation 2: The array arr[] modifies to {-4 – 7 } = {-11}.

Therefore, the last remaining array element is -11.

**Naive Approach:** The simplest approach is to traverse the array until its size reduces to 1 and perform the given operations on the array. After completing the traversal, print the remaining elements. **Time Complexity:** O(N^{2})**Auxiliary Space:** O(1)

**Efficient Approach:** The above approach can be optimized based on the following observations:

- Suppose the given array is
**arr[] = {a, b, c, d}**. Then, performing the operations:

- Now, suppose the array
**arr[] = {a, b, c, d, e}**. Then, performing the operations:

- From the above two observations, it can be concluded that the answer is the
**sum of multiplication of coefficients of terms in the expansion of (x – y)**.^{(N – 1)}and each array element arr[i] - Therefore, the idea is to find the sum of the array
**arr[]**after updating each array element as**(arr[i]***.^{(N – 1)}C_{(i-1)}* (-1)^{i})

Follow the steps below to solve the problem:

- Traverse the array
**arr[]**and update**arr[i]**as**arr[i] = arr[i]***after calculating the^{(N – 1)}C_{(i – 1)}* (-1)^{i }using Pascal’s triangle.^{N}C_{r} - Print the sum of array
**arr[]**.

Below is the implementation of the above approach:

## C++

`// C++ program for the above approach` `#include "bits/stdc++.h"` `using` `namespace` `std;` `// Function to find the last remaining` `// array element after performing` `// the given operations repeatedly` `int` `lastElement(` `const` `int` `arr[], ` `int` `n)` `{` ` ` `// Stores the resultant sum` ` ` `int` `sum = 0;` ` ` `int` `multiplier = n % 2 == 0 ? -1 : 1;` ` ` `// Traverse the array` ` ` `for` `(` `int` `i = 0; i < n; i++) {` ` ` `// Increment sum by arr[i]` ` ` `// * coefficient of i-th term` ` ` `// in (x - y) ^ (N - 1)` ` ` `sum += arr[i] * multiplier;` ` ` `// Update multiplier` ` ` `multiplier` ` ` `= multiplier * (n - 1 - i)` ` ` `/ (i + 1) * (-1);` ` ` `}` ` ` `// Return the resultant sum` ` ` `return` `sum;` `}` `// Driver Code` `int` `main()` `{` ` ` `int` `arr[] = { 3, 4, 2, 1 };` ` ` `int` `N = ` `sizeof` `(arr) / ` `sizeof` `(arr[0]);` ` ` `cout << lastElement(arr, N);` ` ` `return` `0;` `}` |

## Java

`/*package whatever //do not write package name here */` `import` `java.io.*;` `class` `GFG {` ` ` `// Function to find the last remaining` ` ` `// array element after performing` ` ` `// the given operations repeatedly` ` ` `public` `static` `int` `lastElement(` `int` `arr[], ` `int` `n)` ` ` `{` ` ` `// Stores the resultant sum` ` ` `int` `sum = ` `0` `;` ` ` `int` `multiplier = n % ` `2` `== ` `0` `? -` `1` `: ` `1` `;` ` ` `// Traverse the array` ` ` `for` `(` `int` `i = ` `0` `; i < n; i++) {` ` ` `// Increment sum by arr[i]` ` ` `// * coefficient of i-th term` ` ` `// in (x - y) ^ (N - 1)` ` ` `sum += arr[i] * multiplier;` ` ` `// Update multiplier` ` ` `multiplier` ` ` `= multiplier * (n - ` `1` `- i) / (i + ` `1` `) * (-` `1` `);` ` ` `}` ` ` `// Return the resultant sum` ` ` `return` `sum;` ` ` `}` ` ` `// Driver Code` ` ` `public` `static` `void` `main(String[] args)` ` ` `{` ` ` `int` `arr[] = { ` `3` `, ` `4` `, ` `2` `, ` `1` `};` ` ` `int` `N = ` `4` `;` ` ` `System.out.println(lastElement(arr, N));` ` ` `}` `}` `// This code is contributed by aditya7409.` |

## Python3

`# Python 3 program for the above approach` `# Function to find the last remaining` `# array element after performing` `# the given operations repeatedly` `def` `lastElement(arr, n):` ` ` ` ` `# Stores the resultant sum` ` ` `sum` `=` `0` ` ` `if` `n ` `%` `2` `=` `=` `0` `:` ` ` `multiplier ` `=` `-` `1` ` ` `else` `:` ` ` `multiplier ` `=` `1` ` ` `# Traverse the array` ` ` `for` `i ` `in` `range` `(n):` ` ` ` ` `# Increment sum by arr[i]` ` ` `# * coefficient of i-th term` ` ` `# in (x - y) ^ (N - 1)` ` ` `sum` `+` `=` `arr[i] ` `*` `multiplier` ` ` `# Update multiplier` ` ` `multiplier ` `=` `multiplier ` `*` `(n ` `-` `1` `-` `i) ` `/` `(i ` `+` `1` `) ` `*` `(` `-` `1` `)` ` ` `# Return the resultant sum` ` ` `return` `sum` `# Driver Code` `if` `__name__ ` `=` `=` `'__main__'` `:` ` ` `arr ` `=` `[` `3` `, ` `4` `, ` `2` `, ` `1` `]` ` ` `N ` `=` `len` `(arr)` ` ` `print` `(` `int` `(lastElement(arr, N)))` ` ` ` ` `# This code is contributed by SURENDRA_GANGWAR.` |

## C#

`// C# program for the above approach` `using` `System;` `class` `GFG` `{` ` ` `// Function to find the last remaining` ` ` `// array element after performing` ` ` `// the given operations repeatedly` ` ` `public` `static` `int` `lastElement(` `int` `[] arr, ` `int` `n)` ` ` `{` ` ` ` ` `// Stores the resultant sum` ` ` `int` `sum = 0;` ` ` `int` `multiplier = n % 2 == 0 ? -1 : 1;` ` ` `// Traverse the array` ` ` `for` `(` `int` `i = 0; i < n; i++) {` ` ` `// Increment sum by arr[i]` ` ` `// * coefficient of i-th term` ` ` `// in (x - y) ^ (N - 1)` ` ` `sum += arr[i] * multiplier;` ` ` `// Update multiplier` ` ` `multiplier` ` ` `= multiplier * (n - 1 - i) / (i + 1) * (-1);` ` ` `}` ` ` `// Return the resultant sum` ` ` `return` `sum;` ` ` `}` ` ` `// Driver code` ` ` `static` `void` `Main()` ` ` `{` ` ` `int` `[] arr = { 3, 4, 2, 1 };` ` ` `int` `N = 4;` ` ` `Console.WriteLine(lastElement(arr, N));` ` ` `}` `}` `// This code is contributed by susmitakundugoaldanga.` |

## Javascript

`<script>` `// JavaScript program for the above approach` `// Function to find the last remaining` `// array element after performing` `// the given operations repeatedly` `function` `lastElement(arr, n)` `{` ` ` `// Stores the resultant sum` ` ` `let sum = 0;` ` ` `let multiplier = n % 2 == 0 ? -1 : 1;` ` ` `// Traverse the array` ` ` `for` `(let i = 0; i < n; i++)` ` ` `{` ` ` `// Increment sum by arr[i]` ` ` `// * coefficient of i-th term` ` ` `// in (x - y) ^ (N - 1)` ` ` `sum += arr[i] * multiplier;` ` ` `// Update multiplier` ` ` `multiplier` ` ` `= multiplier * (n - 1 - i)` ` ` `/ (i + 1) * (-1);` ` ` `}` ` ` `// Return the resultant sum` ` ` `return` `sum;` `}` `// Driver Code` ` ` `let arr = [ 3, 4, 2, 1 ];` ` ` `let N = arr.length;` ` ` `document.write(lastElement(arr, N));` `// This code is contributed by Surbhi Tyagi.` `</script>` |

**Output:**

4

**Time Complexity:** O(N)**Auxiliary Space:** O(1)