Minimise the Size codechef solution- Consider an array A={a1,a2,…,an}A={a1,a2,…,an} of size n≥1n≥1. If ak=2x−1ak=2x−1 for all 1≤k≤n1≤k≤n, for some integer xx (1≤x≤60)(1≤x≤60), then AA is called interestinginteresting arrayarray. You are given a number CC. Find any interestinginteresting arrayarray AA of minimum possible size such that a1⨁a2⨁…⨁an=Ca1⨁a2⨁…⨁an=C, where ⨁⨁ represents bitwise XOR operation.

Minimise the Size solution codechef

Consider an array A={a1,a2,...,an}A={a1,a2,…,an} of size n1n≥1. If ak=2x1ak=2x−1 for all 1kn1≤k≤n, for some integer xx (1x60)(1≤x≤60), then AA is called interestinginteresting arrayarray.

You are given a number CC. Find any interestinginteresting arrayarray AA of minimum possible size such that a1a2...an=Ca1⨁a2⨁…⨁an=C, where  represents bitwise XOR operation.

If there exists multiple such arrays, output any one.

Input Format Minimise the Size solution codechef

  • First line will contain TT, number of testcases. Then the testcases follow.
  • Each testcase contains single integer CC on a single line.

Output Format Minimise the Size solution codechef

  • For each testcase, on the first line output the minimum possible size of array AA satisfying the given property.
  • On the next line output the elements of array AA in any order.

Constraints

  • 1T1051≤T≤105
  • 0C<2600≤C<260
  • It is guaranteed in the input that sum of lengths of arrays over all testcases does not exceed 106106.

Sample Input 1  Minimise the Size solution codechef

3
1
2
3

Sample Output 1 

1
1
2
1 3
1
3

Explanation Minimise the Size solution codechef

Test caseTest case 1: C=1C=1AA can be {1}{1}

Test caseTest case 2: C=2C=2AA can be {1,3}{1,3}

Test caseTest case 3: C=3C=3AA can be {3}

Leave a Comment