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 21, 22, 23, 24. The most optimal way to divide it into two groups with equal element is 24 + 21 in one group and 22 + 23 in another group giving a minimum possible difference of 6.
Input: n = 8
Output: 30
Explanation:
Here n = 8 which means we have 21, 22, 23, 24, 25, 26, 27, 28. The most optimal way to divide it into two groups with equal element is 28 + 21 + 22 + 23 in one group and 24 + 25 + 26 + 27 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 2N.
- 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 24 to the first group and add N/2 – 1, i.e. 1 more element to this group which is the least which means is 21. - 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 codeint 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 codeif __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:
6
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 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
