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