lets say Given input is n = 6 (n is as large as 100000) My task is to divide {1, 4, 9, 16, 25, 36} into two groups and PRINT these two groups
Possible Solution 1: dividing groups as {1, 9, 36} and {4, 16, 25} which gives abs diff as abs(46 – 45) = 1. So the minimum difference is 1 and the two groups are {1, 9, 36} and {4, 16, 25}
Possible Solution 2: Another Possible Solution is dividing groups as {9, 36} and {1, 4, 16, 25} which gives abs diff as abs(45 – 46) = 1. So the minimum difference is 1 and the two groups are {9, 36} and {1, 4, 16, 25}.
If there are multiple solutions we can print any one. Iam trying to solve it using https://www.geeksforgeeks.org/divide-1-n-two-groups-minimum-sum-difference/ but its not working.
I know that min difference is always 0 or 1 for n >= 6 but how to divide them into two groups.
And can we extend this problem to cubes, fourth powers, so on. if so what is the strategy used