Last Updated: 9 Dec, 2020

Make Groups

Easy

Asked in company

Solve now

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

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

Solve now

Approaches

01 Approach

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 :

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

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

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’).
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).
Finally, return the minimum of both recursive calls.

Solve now

02 Approach

Find the sum of all elements upto ‘N’ and divide it by 2 which will represent as the ‘SUM’ of a group. Add elements in the first group starting from ‘N’ till the ‘SUM’ is greater than the element else add it to another group.

Here is the algorithm :

Create a variable (say, ‘SUM’), initialise it with N*(N+1)/2 (Sum of first ‘N’ natural numbers)
Create a variable (say, ‘group1Sum’) and initialise it with SUM/2 which represents the temporary sum of elements of the first group.
Create two variables (say, ‘GROUP1’ and ‘GROUP2’) which will store the sum of both groups and initialise them to 0.
Run a loop from ‘N’ to 0 (say, iterator = ‘i’) :
1. Check if ‘group1Sum’ is greater than equal to ‘i’ :
  1. Update ‘GROUP1’ as ‘GROUP1’ + ‘i’
  2. Update ‘group1Sum’ as ‘group1Sum’ - ‘i’
2. Else :
  1. Update ‘GROUP2’ as ‘GROUP2’ + ‘i’.
Finally, return ‘ABS(‘GROUP1’ - ‘GROUP2’).

Solve now