Odd Sum solution codechef

Odd Sum solution codechef

Given an integer NN, consider all arrays AA of size NN such that:

  • All the elements are non-negative and distinct.
  • All prefix sums are odd. Formally, for all ii such that 1iN1≤i≤Nij=1Ai∑j=1iAi is odd.

Among all possible arrays AA, output the smallest possible sum of the elements of the array.

Note: Since the Input/Output may be large, it is preferred to use fast I/O.

Input Format

Odd Sum solution codechef

  • The first line contains TT – the number of test cases. Then the test cases follow.
  • The first line of each test case contains NN – the size of the array.

Output Format

Odd Sum solution codechef

For each test case, output on one line the smallest sum among all arrays satisfying the constraints.

Constraints

Odd Sum solution codechef

  • 1T1061≤T≤106
  • 1N1091≤N≤109

Sample Input 1 

1
3

Sample Output 1

Odd Sum solution codechef

3

Explanation

  • Test case 11: A possible array is [1,2,0][1,2,0][1,0,0][1,0,0] is not valid because 00 occurs twice in it; [0,1,2][0,1,2] is not valid because the prefix sum until the first index is 00, which is even. Another possible array is [5,2,4][5,2,4][1,2,0][1,2,0] yields the sum 33, and we can prove that there are no valid arrays that have sum less than 33.
  • For Solution

    Click Here!

Leave a Comment