BPM  Bipartite Permutation
Given a positive integer N, consider any permutation of all the numbers from 1 to N. It is required to create two partitions, P_{1} and P_{2}, from these numbers such that sum(P_{1}) – sum(P_{2}) is minimum, where sum(X) denotes the summation of all the numbers in partition X. A partition is defined to be a nonempty subset of the permutation. In other words, find the minimum absolute difference between the summation of all the numbers in each partition. Note that you cannot leave out any number, every number from 1 to N must be part of exactly one partition.
1 ≤ T ≤ 1000
2 ≤ N ≤ 10^{9}
Bipartite Permutation (Hard)
Input
The first line contains an integer T, denoting the number of test cases. Each of the next subsequent T lines contain a positive integer N.Constraints
Output
For each test case, first print the case number followed by the minimum absolute difference.Sample Input
5 2 3 4 5 6
Sample Output
Case 1: 1 Case 2: 0 Case 3: 0 Case 4: 1 Case 5: 1
Challenge
Try the harder version here:Bipartite Permutation (Hard)
hide comments
Waseem Ahmed:
20210924 06:10:50
Can be solved in O(1) time 

sonukumar:
20210125 21:21:06
easiest one


vineetjai:
20200906 06:45:33
Nice one. Got me on Case #1 instead of Case 1. 

aknov711:
20200812 15:50:41
Amazing! Last edit: 20200813 09:08:16 

Shubham Jadhav:
20200626 13:57:57
Nice problem. Last edit: 20200627 00:22:07 

offamitkumar:
20200624 06:20:17
Can you check whether my logic correct or not?


robosapien:
20200623 00:56:02
nice problem. Can we prove this?


ksaikiranr:
20200331 20:08:37
my linear solution is giving me TLE

Added by:  sgtlaugh 
Date:  20191116 
Time limit:  1s 
Source limit:  50000B 
Memory limit:  1536MB 
Cluster:  Cube (Intel G860) 
Languages:  All 
Resource:  Own Problem 