Make Groups

Easy
0/40
Average time to solve is 10m
profile
Contributed by
37 upvotes
Asked in company
D.E.Shaw

Problem statement

Given a positive integer ‘N’. Divide numbers from 1 to ‘N’ in two groups such that the absolute difference of sum of each group is minimum and print the absolute difference.

Example :

If ‘N’ : 3
Then the two groups can be : {3} and {2, 1}
The absolute difference of sum between above two groups is : 0
Detailed explanation ( Input/output format, Notes, Images )
Input Format : 
The first line of input contains an integer ‘T’ representing the number of test cases.
Then the test cases follow :
The only line of each test case contains a single integer ‘N’.
Output Format : 
For each test case, print the minimum absolute difference of sum of each group.
Note : 
You do not need to print anything, it has already been taken care of. Just implement the given function.
Constraints : 
1 <= T <= 10^2
2 <= N <= 10^4

Time Limit : 1 sec
Sample Input 1 :
2
4
2
Sample Output 1 :
0
1
Explanation For Sample Input 1 :
For first test case,
First group can be {1, 4}, sum of first group is  : 4 + 1 = 5
Second group can be {2, 3}, sum of second group is : 3 + 2 = 5
Minimum absolute difference : |5 - 5| = 0

For second test case,
First group can be {1}, sum of first group is : 1
Second group can be {2}, sum of second group is: 2
Minimum absolute difference : |1 - 2| = 1
Sample Input 2 :
1
5
Sample Output 2 :
1
Explanation For Sample Input 2 :
First group can be {2, 5}, sum of first group is : 5 + 2 = 7
Second group can be {1, 3, 4}, sum of second group is : 4 + 3 + 1 = 8
Minimum absolute difference : |7 - 8| = 1
Hint

Try to find all the possible sums.

Approaches (2)
Brute Force

The naive approach for this is to generate all the possible sums by including i’th number in a group or not, and then find the optimal solution. 


Here is the algorithm :

 

  1. Create a variable (say, ‘SUM’), initialise it with N*(N+1)/2  (Sum of first ‘N’ natural numbers)
  2. Call the ‘HELPER’ function, HELPER(‘SUM’, ‘N’, 0).

 

HELPER(‘SUM’, ‘i’, ‘group1Sum’)

 

  1. Base condition : if ‘i’ is equal to 0. (We have reached the last number).
    • Return, ABS((‘SUM’ - ‘group1Sum’) - ‘group1Sum’). ( Sum of group2 will be equal to ‘SUM’ - ‘group1Sum’. Therefore, the absolute difference of sum of each group will be ABS(‘group2Sum’ - ‘group1Sum’) i.e. abs((‘SUM’ - ‘group1Sum’) - ‘group1Sum’).
  2. Call the recursive ‘HELPER’ function, while including the ‘i’’th in ‘GROUP1’ and while not including it in a ‘GROUP1’. (We have 2 choices with us, whether to include a number in a group or not).
  3. Finally, return the minimum of both recursive calls.
Time Complexity

O(2^N), where ‘N’ denotes the given positive integer.

 

Each number has two choices, whether to include it in a ‘GROUP1’ or not. There are total ‘N’ numbers present with us, so the total possible combinations will be 2*2*2… (‘N’ times). Therefore, the overall time complexity will be O(2^N).

Space Complexity

O(N).

 

This space is used to store the recursion stack. Our algorithm works in a depth - first way, so we cannot have more than ‘N’ recursive calls on the stack as the total numbers present can be at max ‘N’. Therefore, the overall space complexity will be O(N).

Code Solution
(100% EXP penalty)
Make Groups
Full screen
Console