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, P1 and P2, from these numbers such that |sum(P1) – sum(P2)| is minimum, where sum(X) denotes the summation of all the numbers in partition X. A partition is defined to be a non-empty 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.

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

  • 1 ≤ T ≤ 1000
  • 2 ≤ N ≤ 109
  • 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: 2021-09-24 06:10:50

    Can be solved in O(1) time

    sonukumar: 2021-01-25 21:21:06

    easiest one
    I got AC with O(1) time

    Last edit: 2021-01-25 21:21:22
    vineetjai: 2020-09-06 06:45:33

    Nice one. Got me on Case #1 instead of Case 1.

    aknov711: 2020-08-12 15:50:41

    Amazing!

    Last edit: 2020-08-13 09:08:16
    Shubham Jadhav: 2020-06-26 13:57:57

    Nice problem.

    Last edit: 2020-06-27 00:22:07
    offamitkumar: 2020-06-24 06:20:17

    Can you check whether my logic correct or not?
    Finally Solved.. Amazing problem.

    -> Sorry just seeing this. Great work, congrats!

    Last edit: 2020-07-30 12:52:50
    robosapien: 2020-06-23 00:56:02

    nice problem. Can we prove this?

    -> Sure we can. Is that very hard to prove?

    Last edit: 2020-06-23 19:43:47
    ksaikiranr: 2020-03-31 20:08:37

    my linear solution is giving me TLE
    how to solve this?

    -> Obviously, by using something faster than that!

    Last edit: 2020-04-17 10:18:41

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