Reduce given Array by replacing adjacent elements with their difference

Given an array arr[] consisting of N elements(such that N = 2^k for some k ? 0), the task is to reduce the array and find the last remaining element after merging all elements into one. The array is reduced by performing the following operation:

• Merge the adjacent elements i.e merge elements at indices 0 and 1 into one, 2 and 3 into one and so on. 
• Upon merging the newly formed element will become the absolute difference between the two elements merged.

Examples:

Input: N = 4, arr[] = [1, 2, 3, 4]
Output: 0
Explanation: First operation:
On merging 1st and 2nd elements we will have a element with value1. 
On merging 3rd and 4th elements, we will have a element with value1. 
Therefore, we are left with two elements where each of them having cost 1.
Second operation:
On merging the 1st and 2nd elements we will get a new element with value 0.
This is because both elements had the same value of 1.

Input: N = 1, arr[] = [20]
Output: 20
Explanation: We can't perform any operation because performing an operation requires at least 2 elements. Hence, 20 is cost of the last remaining element

Approach: This problem can be solved using the Divide and Conquer approach.

• Create a recursive function.
  • The base condition for recursion will be if the size of the array is 1 then the answer will be the only array element in it.
  • Return the absolute difference between the first half of the array and the second half of the array by calling the recursive function for both halves.
  • Merge both halves and get the answer.

Below is the implementation of the above approach:

// C++ code to implement the approach #include <bits/stdc++.h> using namespace std; // Function to get the last remaining element // by using divide and conquer int f(int l, int e, int a[]) {  // Base condition  if (l == e)  return a[l];  return abs(f(l, l + (e - l) / 2, a)  - f(l + (e - l) / 2 + 1, e, a)); } int find(int n, int a[]) {  return f(0, n - 1, a); } // Driver code int main() {  int arr[] = { 1, 2, 3, 4 };  int N = sizeof(arr) / sizeof(arr[0]);  // Function Call  cout << find(N, arr);  return 0; } 

// Java code to implement the approach import java.io.*; class GFG {  // Function to get the last remaining element  // by using divide and conquer  static int f(int l, int e, int[] a)  {  // Base condition  if (l == e) {  return a[l];  }  return Math.abs(f(l, l + (e - l) / 2, a)  - f(l + (e - l) / 2 + 1, e, a));  }  static int find(int n, int[] a)  {  return f(0, n - 1, a);  }  public static void main(String[] args)  {  int[] arr = { 1, 2, 3, 4 };  int N = arr.length;  // Function call  System.out.print(find(N, arr));  } } // This code is contributed by lokeshmvs21. 

# Python code to implement the approach # Function to get the last remaining element # by using divide and conquer import sys sys.setrecursionlimit(1500) def f(l, e, a): # Base condition if (l == e): return a[l] return abs(f(l, l + (e - l) // 2, a) - f(l + (e - l) // 2 + 1, e, a)) def find(n, a): return f(0, n - 1, a) # Driver code if __name__ == "__main__": arr = [1, 2, 3, 4] N = len(arr) # Function Call print(find(N, arr)) # This code is contributed by Rohit Pradhan 

// C# implementation using System; public class GFG{  // Function to get the last remaining element  // by using divide and conquer  public static int f(int l, int e, int []a)  {    // Base condition  if (l == e)  return a[l];  return Math.Abs(f(l, l + (e - l) / 2, a)  - f(l + (e - l) / 2 + 1, e, a));  }  public static int find(int n, int []a)  {  return f(0, n - 1, a);  }  static public void Main (){  int []arr = { 1, 2, 3, 4 };  int N = arr.Length;  // Function Call  Console.WriteLine(find(N, arr));  } } // This code is contributed by ksam24000 

// Javascript code to implement the approach // Function to get the last remaining element // by using divide and conquer function f(l, e, a) {  // Base condition  if (l == e) {  return a[l];  }  return Math.abs(f(l, l + Math.floor((e - l) / 2), a)  - f(l + Math.floor((e - l) / 2) + 1, e, a)); } function find(n, a) {  return f(0, n - 1, a); } let arr = [1, 2, 3, 4]; let N = arr.length; // Function call console.log(find(N, arr)); // This code is contributed by Saurabh Jaiswal 

0

Time Complexity: O(2^log₂N)
Auxiliary Space: O(N)