Horje
Reduce given Array by replacing adjacent elements with their difference

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 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

// 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.

Python3

# 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#

// 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

// 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

Output

0

Time Complexity: O(2log2N)
Auxiliary Space: O(N)


 


Reffered: https://www.geeksforgeeks.org

Divide And Conquer

Related
Sort the array using slow sort Sort the array using slow sort
Print all array elements appearing more than N / K times Print all array elements appearing more than N / K times
Minimum count of elements required to obtain the given Array by repeated mirror operations Minimum count of elements required to obtain the given Array by repeated mirror operations
Calculate weight of parenthesis based on the given conditions Calculate weight of parenthesis based on the given conditions
Divide N into K parts in the form (X, 2X, ... , KX) for some value of X Divide N into K parts in the form (X, 2X, ... , KX) for some value of X

Type:
 Geek
Category:
 Coding
Sub Category:
 Tutorial
Uploaded by:
 Admin
Views:
 13



 

Horje