Split N powers of 2 into two subsets such that their difference of sum is minimum

0 0 5 minutes read

Given an even number N, the task is to split all N powers of 2 into two sets such that the difference of their sum is minimum.
Examples:

Input: n = 4
Output: 6
Explanation:
Here n = 4 which means we have 2¹, 2², 2³, 2⁴. The most optimal way to divide it into two groups with equal element is 2⁴ + 2¹ in one group and 2² + 2³ in another group giving a minimum possible difference of 6.
Input: n = 8
Output: 30
Explanation:
Here n = 8 which means we have 2¹, 2², 2³, 2⁴, 2⁵, 2⁶, 2⁷, 2⁸. The most optimal way to divide it into two groups with equal element is 2⁸ + 2¹ + 2² + 2³ in one group and 2⁴ + 2⁵ + 2⁶ + 2⁷ in another group giving a minimum possible difference of 30.

Approach: To solve the problem mentioned above we have to follow the steps given below:

In the first group add the largest element that is 2^N.
After adding the first number in one group, add N/2 – 1 more elements to this group, where the elements has to start from the least power of two or from the beginning of the sequence.
For example: if N = 4 then add 2⁴ to the first group and add N/2 – 1, i.e. 1 more element to this group which is the least which means is 2¹.
The remaining element of the sequence forms the elements of the second group.
Calculate the sum for both the groups and then find the absolute difference between the groups which will eventually be the minimum.

Below is the implementation of the above approach:

C++

// C++ program to find the minimum
// difference possible by splitting
// all powers of 2 up to N into two 
// sets of equal size 
#include<bits/stdc++.h>
using namespace std;
 
void MinDiff(int n)
{
 
    // Store the largest
    int val = pow(2, n);
     
    // Form two separate groups
    int sep = n / 2;
     
    // Initialize the sum 
    // for two groups as 0
    int grp1 = 0;
    int grp2 = 0;
     
    // Insert 2 ^ n in the
    // first group
    grp1 = grp1 + val;
     
    // Calculate the sum of
    // least n / 2 -1 elements
    // added to the first set 
    for(int i = 1; i < sep; i++)
       grp1 = grp1 + pow(2, i);
         
    // Sum of remaining
    // n / 2 - 1 elements
    for(int i = sep; i < n; i++)
       grp2 = grp2 + pow(2, i);
         
    // Min Difference between
    // the two groups
    cout << (abs(grp1 - grp2));
} 
 
// Driver code
int main()
{
    int n = 4;
    MinDiff(n); 
}
 
// This code is contributed by Bhupendra_Singh

Java

// Java program to find the minimum 
// difference possible by splitting 
// all powers of 2 up to N into two  
// sets of equal size  
import java.lang.Math; 
 
class GFG{ 
 
public static void MinDiff(int n) 
{ 
 
    // Store the largest 
    int val = (int)Math.pow(2, n); 
     
    // Form two separate groups 
    int sep = n / 2; 
     
    // Initialize the sum 
    // for two groups as 0 
    int grp1 = 0; 
    int grp2 = 0; 
     
    // Insert 2 ^ n in the 
    // first group 
    grp1 = grp1 + val; 
     
    // Calculate the sum of 
    // least n / 2 -1 elements 
    // added to the first set 
    for(int i = 1; i < sep; i++) 
       grp1 = grp1 + (int)Math.pow(2, i); 
         
    // Sum of remaining 
    // n / 2 - 1 elements 
    for(int i = sep; i < n; i++) 
       grp2 = grp2 + (int)Math.pow(2, i); 
         
    // Min difference between 
    // the two groups 
    System.out.println(Math.abs(grp1 - grp2)); 
} 
 
// Driver Code 
public static void main(String args[]) 
{ 
    int n = 4; 
     
    MinDiff(n); 
} 
} 
 
// This code is contributed by grand_master

Python3

# Python3 program to find the minimum
# difference possible by splitting
# all powers of 2 up to N into two 
# sets of equal size  
 
def MinDiff(n):
     
    # Store the largest
    val = 2 ** n
     
    # Form two separate groups
    sep = n // 2
     
    # Initialize the sum 
    # for two groups as 0
    grp1 = 0
    grp2 = 0
     
    # Insert 2 ^ n in the
    # first group
    grp1 = grp1 + val
     
    # Calculate the sum of
    # least n / 2 -1 elements
    # added to the first set 
    for i in range(1, sep):
        grp1 = grp1 + 2 ** i
         
     
    # sum of remaining
    # n / 2 - 1 elements
    for i in range(sep, n):
        grp2 = grp2 + 2 ** i
         
    # Min Difference between
    # the two groups
    print(abs(grp1 - grp2))     
     
# Driver code
if __name__=='__main__':
    n = 4
    MinDiff(n)

C#

// C# program to find the minimum 
// difference possible by splitting 
// all powers of 2 up to N into two 
// sets of equal size 
using System;
class GFG{ 
 
public static void MinDiff(int n) 
{ 
 
    // Store the largest 
    int val = (int)Math.Pow(2, n); 
     
    // Form two separate groups 
    int sep = n / 2; 
     
    // Initialize the sum 
    // for two groups as 0 
    int grp1 = 0; 
    int grp2 = 0; 
     
    // Insert 2 ^ n in the 
    // first group 
    grp1 = grp1 + val; 
     
    // Calculate the sum of 
    // least n / 2 -1 elements 
    // added to the first set 
    for(int i = 1; i < sep; i++) 
    grp1 = grp1 + (int)Math.Pow(2, i); 
         
    // Sum of remaining 
    // n / 2 - 1 elements 
    for(int i = sep; i < n; i++) 
    grp2 = grp2 + (int)Math.Pow(2, i); 
         
    // Min difference between 
    // the two groups 
    Console.Write(Math.Abs(grp1 - grp2)); 
} 
 
// Driver Code 
public static void Main() 
{ 
    int n = 4; 
     
    MinDiff(n); 
} 
} 
 
// This code is contributed by Akanksha_Rai

Javascript

<script>
// javascript program to find the minimum 
// difference possible by splitting 
// all powers of 2 up to N into two  
// sets of equal size  
 
    function MinDiff(n) 
    {
 
        // Store the largest
        var val = parseInt( Math.pow(2, n));
 
        // Form two separate groups
        var sep = n / 2;
 
        // Initialize the sum
        // for two groups as 0
        var grp1 = 0;
        var grp2 = 0;
 
        // Insert 2 ^ n in the
        // first group
        grp1 = grp1 + val;
 
        // Calculate the sum of
        // least n / 2 -1 elements
        // added to the first set
        for (i = 1; i < sep; i++)
            grp1 = grp1 + parseInt( Math.pow(2, i));
 
        // Sum of remaining
        // n / 2 - 1 elements
        for (i = sep; i < n; i++)
            grp2 = grp2 + parseInt( Math.pow(2, i));
 
        // Min difference between
        // the two groups
        document.write(Math.abs(grp1 - grp2));
    }
 
    // Driver Code
        var n = 4;
        MinDiff(n);
 
// This code is contributed by gauravrajput1
</script>

Output:

Time complexity: O(N*logN) because it is using a pow(2,i) function inside a for loop
Auxiliary Space: O(1)

Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 zambiatek!