Given an array arr[] consisting of N elements(such that N = 2k 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++
// C++ code to implement the approach#include <bits/stdc++.h>using namespace std;// Function to get the last remaining element// by using divide and conquerint 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 codeint main(){ int arr[] = { 1, 2, 3, 4 }; int N = sizeof(arr) / sizeof(arr[0]); // Function Call cout << find(N, arr); return 0;} |
Java
// Java code to implement the approachimport 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. |
Python3
# Python code to implement the approach# Function to get the last remaining element# by using divide and conquerimport syssys.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 codeif __name__ == "__main__": arr = [1, 2, 3, 4] N = len(arr) # Function Call print(find(N, arr))# This code is contributed by Rohit Pradhan |
C#
// C# implementationusing 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
// Javascript code to implement the approach// Function to get the last remaining element// by using divide and conquerfunction 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 callconsole.log(find(N, arr));// This code is contributed by Saurabh Jaiswal |
0
Time Complexity: O(2log2N)
Auxiliary Space: O(N)
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
