Tuesday, 19 Oct 2021

# Minimize difference between two sequences obtained by splitting first N powers of 2

Minimize difference between two sequences obtained by splitting first N powers of 2
Given a positive even number N, the task is to split the first N powers of 2 into two equal sequences such that the absolute difference between their sum is minimized. Print the minimum difference obtained.
Examples:

Input: N = 2Output: 2Explanation:The sequence is {2, 4}.Only possible way to split the sequence is {2}, {4}. Therefore, difference = 4 − 2 = 2.
Input: N = 4Output: 6Explanation:The sequence is {2, 4, 8, 16}.The most optimal way is to split the sequence as {2, 16}, {4, 8}. The difference is (2 + 16) − (4 + 8) = 6.

Naive Approach: The simplest approach to solve this problem is to generate all possible combinations of N/2 elements of the sequence and store their sum. Then, find the minimum difference among all the sum of the pairs.Time Complexity: O(2N)Auxiliary Space: O(N)
Approach: The above approach can also be optimized as per the following observations:
As 2N is greater than the sum of all the other elements combined:

The subarray having the largest element will always have a larger sum. Therefore, to minimize the differences between their sum, the idea is to put the (N/2 – 1) smallest elements into the subarray with the largest element.
Follow the steps below to solve the problem:Initialize two variables, sum1 = 0 and sum2 = 0, to store the sum of the first subarray and the second subarray respectively.
Add the sum of and 2N to the variable sum1.
Add the sum of to the variable sum2.
After completing the above steps, print the difference between sum1 and sum2.
Below is the implementation of the above approach:

C++

#include
using namespace std;

void minimumDifference(int N)
{

int sum1 = (1