Permutation XOR Sum solution codechef- For a permutation PP of integers from 11 to NN, let’s define its value as (1⊕P1)+(2⊕P2)+…+(N⊕PN)(1⊕P1)+(2⊕P2)+…+(N⊕PN). Given NN, find the maximum possible value of the permutation of integers from 11 to NN. As a reminder, ⊕⊕ denotes the bitwise XOR operation

Permutation XOR Sum solution codechef

For a permutation PP of integers from 11 to NN, let’s define its value as (1P1)+(2P2)++(NPN)(1⊕P1)+(2⊕P2)+…+(N⊕PN).

Given NN, find the maximum possible value of the permutation of integers from 11 to NN.

As a reminder,  denotes the bitwise XOR operation

Input Format Permutation XOR Sum solution codechef

The first line of the input contains a single integer TT  the number of test cases. The description of test cases follows.

The only line of each test case contains a single integer NN.

Output Format

For each test case, output the maximum possible value of the permutation of integers from 11 to NN.

Constraints Permutation XOR Sum solution codechef

  • 1T1051≤T≤105
  • 1N1091≤N≤109.

Subtasks

Subtask 1 (60 points): The sum of NN over all test cases doesn’t exceed 106106Subtask 2 (40 points): No additional constraints.

Sample Input 1 

5
1
2
3
4
29012022

Sample Output 1 

0
6
6
20
841697449540506

Explanation Permutation XOR Sum solution codechef

For N=1N=1, the only such permutation is P=(1)P=(1), its value is 11=01⊕1=0.

For N=2N=2, the permutation with the best value is P=(2,1)P=(2,1), with value 12+21=61⊕2+2⊕1=6.

For N=3N=3, the permutation with the best value is P=(2,1,3)P=(2,1,3), with value 12+21+33=61⊕2+2⊕1+3⊕3=6.

For N=4N=4, the permutation with the best value is P=(2,1,4,3)P=(2,1,4,3), with value 12+21+34+43=201⊕2+2⊕1+3⊕4+4⊕3=20.

Leave a Comment

Your email address will not be published.