FINXOR - Editorial

editorial
, , , , , ,
1

PROBLEM LINK:

Practice
Div-2 Contest
Div-1 Contest
Video Editorial

Author and Editorialist: Kritagya Agarwal
Tester: Suchan Park

DIFFICULTY:

Easy - Medium

PREREQUISITES:

Bitwise Xor, Linear Equations

PROBLEM:

Given an array A of size N.

We need to find the value of A[1]⊕A[2]⊕.....⊕A[N] , where ⊕ represents Bitwise Xor Operation by asking at most 20 queries.

In eack query we can ask the value of A[1]⊕K + A[2]⊕K + ..... + A[N]⊕K, (1 \le K \le 2*10^6)

QUICK EXPLANATION:

  • In i^{th} query, choose K = 2^{i-1} for all 1 \le i \le 20
  • Form linear equations using queries with variables as x_k (0 \le k \le 19), representing the number of elements in array with k^{th} bit ON.
  • Find the parity or value of x_k by solving linear equations. If the parity of x_k is Odd, then answer will have k^{th} bit ON.

EXPLANATION:

Since A[i] \le10^6, there can be at most 20 bits in binary representation of A[i] for all 1 \le i \le N.

Lets, define x_k for 0 \le k \le 19, as the number of elements in array A with k^{th} bit ON.

If we know the values of x_k, then if parity of x_k is Odd, answer will have k^{th} bit ON. This holds due to the property of xor operator.

To find the value of x_k :-

In i^{th} query, choose K = 2^{i-1}. Suppose answer to given query is q_i. Using the property of xor operator, we can claim that :-

  • 2^{0} \cdot x_0 + 2^{1} \cdot x_1 + ..... + 2^{i} \cdot (N - x_i)+ ....... + 2^{19} \cdot x_{19} = q_i

as all the elements with i^{th} bit OFF will contribute to q_i due to property of Xor.

Above equation can be rewritten as :-

  • 2^{0} \cdot x_0 + 2^{1} \cdot x_1 + ..... - 2^{i} \cdot x_i + ....... + 2^{19} \cdot x_{19} = q_i - N \cdot 2^{i}

Thus, using 20 queries, we get 20 linear equations with variables as x_k. We can solve these linear equations to get the value of x_k.

Any system of Linear Equations A \cdot x = b can be represented as :

A = \begin{bmatrix} a_{11} & a_{12} & .... & a_{1n} \\ a_{21} & a_{22} & .... & a_{2n}\\ a_{31} & a_{32} & .... & a_{3n}\\ .. & ... & .... & ...\\ a_{m1} & a_{m2} & .... & a_{mn}\\ \end{bmatrix} , x = \begin{bmatrix} x_1 \\ x_2 \\ .... \\ .... \\ x_n \\ \end{bmatrix} , b = \begin{bmatrix} b_1 \\ b_2 \\ .... \\ .... \\ b_m \\ \end{bmatrix}

So, we have given values of A, x, b here :

A = \begin{bmatrix} -2^0 & 2^1 & .... & 2^{19} \\ 2^0 & -2^1 & .... & 2^{19}\\ 2^0 & 2^1 & .... & 2^{19}\\ .. & ... & .... & ...\\ 2_0 & 2^1 & .... & -2^{19}\\ \end{bmatrix} , x = \begin{bmatrix} x_0 \\ x_1 \\ .... \\ .... \\ x_{19} \\ \end{bmatrix} , b = \begin{bmatrix} q_0 - N \cdot2^0 \\ q_1 - N \cdot2^1\\ .... \\ .... \\ q_{19} - N \cdot2^19 \\ \end{bmatrix}

Note : det(A) != 0, hence there exists a unique solution to system of Linear Equations.

In Python, linear equation can be solved using linalg Function .

Note : Don’t forget to use around function to get integer values of x_k.

ALTERNATE EXPLANATION 1:

Thanks to Navneel for this approach.

Another possible method (without explicitly carrying out Gaussian Elimination) is to use the following:

Suppose the query is 1 2^k for k \in \{0, 1, \dots, 19\}. Then if the number of elements whose i^\mathrm{th}
bit is on is x_k , then the difference between the answer of the query (say v_k ) and the sum of all numbers would be (n - 2 \cdot x_k).2^k

Note that the sum of all numbers is in fact \sum_{k = 0}^{19} x_k.2^k so we have :-

v_k - n.2^k = x_0.2^0 + ... + x_{k-1}.2^{k-1} - x_k.2^k + ... + x_n.2^n

Treating this as a set of linear equations in x_i's, we write it as

A = \begin{bmatrix} -2^0 & 2^1 & .... & 2^{19} \\ 2^0 & -2^1 & .... & 2^{19}\\ 2^0 & 2^1 & .... & 2^{19}\\ .. & ... & .... & ...\\ 2_0 & 2^1 & .... & -2^{19}\\ \end{bmatrix} , x = \begin{bmatrix} x_0 \\ x_1 \\ .... \\ .... \\ x_{19} \\ \end{bmatrix} , b = \begin{bmatrix} v_0 - n \cdot2^0 \\ v_1 - n \cdot2^1\\ .... \\ .... \\ v_{19} - n \cdot2^19 \\ \end{bmatrix}

Note that the inverse of the 20 \cdot 20 matrix i.e. A is in fact :

A' = 1/(18 \cdot 2^{20})\begin{bmatrix} -17.2^{17} & 2^{17} & .... & 2^{17} \\ 2^{16} & -16.2^{16} & .... & 2^{16}\\ 2^{15} & 2^{15} & .... & 2^{15}\\ .. & ... & .... & ...\\ 1 &1 & .... & -17\\ \end{bmatrix}

So our final results if x = A'.b. We can get the parity of x_k from this. If x_k is Odd, then k^{th} bit is ON in answer.

ALTERNATE EXPLANATION 2

Thanks to Divyansh for this approach.

SOLUTIONS:

Setter's Solution (Python) 
import numpy as np
 
def ask_query(k):
    print(1, k)
    ans = int(input())
    if ans == -1:
        exit()
    return ans
 
a = np.array([
    [-1,2,4,8,16,32,64,128,256,512,1024,2048,4096,8192,16384,32768,65536,131072,262144,524288],
    [1,-2,4,8,16,32,64,128,256,512,1024,2048,4096,8192,16384,32768,65536,131072,262144,524288],
    [1,2,-4,8,16,32,64,128,256,512,1024,2048,4096,8192,16384,32768,65536,131072,262144,524288],
    [1,2,4,-8,16,32,64,128,256,512,1024,2048,4096,8192,16384,32768,65536,131072,262144,524288],
    [1,2,4,8,-16,32,64,128,256,512,1024,2048,4096,8192,16384,32768,65536,131072,262144,524288],
    [1,2,4,8,16,-32,64,128,256,512,1024,2048,4096,8192,16384,32768,65536,131072,262144,524288],
    [1,2,4,8,16,32,-64,128,256,512,1024,2048,4096,8192,16384,32768,65536,131072,262144,524288],
    [1,2,4,8,16,32,64,-128,256,512,1024,2048,4096,8192,16384,32768,65536,131072,262144,524288],
    [1,2,4,8,16,32,64,128,-256,512,1024,2048,4096,8192,16384,32768,65536,131072,262144,524288],
    [1,2,4,8,16,32,64,128,256,-512,1024,2048,4096,8192,16384,32768,65536,131072,262144,524288],
    [1,2,4,8,16,32,64,128,256,512,-1024,2048,4096,8192,16384,32768,65536,131072,262144,524288],
    [1,2,4,8,16,32,64,128,256,512,1024,-2048,4096,8192,16384,32768,65536,131072,262144,524288],
    [1,2,4,8,16,32,64,128,256,512,1024,2048,-4096,8192,16384,32768,65536,131072,262144,524288],
    [1,2,4,8,16,32,64,128,256,512,1024,2048,4096,-8192,16384,32768,65536,131072,262144,524288],
    [1,2,4,8,16,32,64,128,256,512,1024,2048,4096,8192,-16384,32768,65536,131072,262144,524288],
    [1,2,4,8,16,32,64,128,256,512,1024,2048,4096,8192,16384,-32768,65536,131072,262144,524288],
    [1,2,4,8,16,32,64,128,256,512,1024,2048,4096,8192,16384,32768,-65536,131072,262144,524288],
    [1,2,4,8,16,32,64,128,256,512,1024,2048,4096,8192,16384,32768,65536,-131072,262144,524288],
    [1,2,4,8,16,32,64,128,256,512,1024,2048,4096,8192,16384,32768,65536,131072,-262144,524288],
    [1,2,4,8,16,32,64,128,256,512,1024,2048,4096,8192,16384,32768,65536,131072,262144,-524288]
    ])
    
 
for _ in range(int(input())):
    x = 1
    b = [None]*20
    n = int(input())
 
 
    for i in range(0,20):
        b[i] = ask_query(x)-n*x
        x *= 2
 
    b = np.array(b)
    c = np.linalg.solve(a, b)
    c = np.around(c)
 
    ans = 0
    x = 1
 
    for i in range(0,20):
        if(c[i]%2 != 0):
            ans += x;
        x *= 2
 
    print(2,ans)
 
    if int(input()) == -1:
        exit()
Tester Solution (Kotlin) 
import kotlin.system.exitProcess

class FINXOR_SOLVER(val ask: (Int) -> Int) {
    fun solve(N: Int): Int {
        val sum = ask(1 shl 20) - (1 shl 20) * N
        var answer = sum % 2
        for (b in 1 until 20) {
            val diff = ask(1 shl b) - sum
            require(diff and ((1 shl b) - 1) == 0)
            val num_ones = (N - (diff shr b)) / 2
            if (num_ones % 2 == 1) {
                answer = answer xor (1 shl b)
            }
        }
        return answer
    }
}

fun main(args: Array<String>) {
    val T = readLine()!!.toInt()
    require(T in 1..100)
    repeat(T) {
        val solver = FINXOR_SOLVER { k: Int ->
            println("1 $k")
            val ret = readLine()!!.toInt()
            if (ret == -1) {
                exitProcess(0)
            }
            ret
        }
        val N = readLine()!!.toInt()
        val answer = solver.solve(N)
        println("2 $answer")
        val response = readLine()!!.toInt()
        if (response == -1) {
            exitProcess(0)
        }
    }
}
Alternative Approach (C++) 
#include <bits/stdc++.h>
using namespace std;
 
#define int long long
 
int32_t main() {
    
    int t;
    cin >> t;
    
    int m[20][20] = {0};
    
    m[19][19] = -17;
    for (int i = 0; i < 19; ++i) {
        m[19][i] = 1;
    }
 
    for (int i = 18; ~i; --i) {
        for (int j = 0; j < 20; ++j) {
            m[i][j] = m[i + 1][(j + 1) % 20] * 2;
        }
    }
 
    int div = 18 << 20;
 
    while (t--) {
        int n;
        cin >> n;
        int s;
        vector<int> v(20);
        for (int i = 19; ~i; --i) {
            cout << 1 << " " << (1 << i) << endl;
            cin >> s;
            s -= (n << i);
            v[i] = s;
        }
        int ans = 0;
        for (int i = 0; i < 20; ++i) {
            int cur = 0;
            for (int j = 0; j < 20; ++j) {
                cur += m[i][j] * v[j];
            }
            cur /= div;
            ans += (cur & 1) << i;
        }
        cout << 2 << " " << ans << endl;
        cin >> s;
        assert(s == 1);
    }
    return 0;
}

Video Editorial

1 Like
2

Another possible method (without explicitly carrying out Gaussian Elimination) is to use the following:

For n \ge 3, the inverse of

\begin{bmatrix} -1 & 2 & \cdots & 2^{n-1}\\ 1 & -2 & \cdots & 2^{n - 1}\\ \vdots & \vdots & \ddots & \vdots\\ 1 & 2 & \cdots & -2^{n - 1} \end{bmatrix}

is

\dfrac{1}{(n - 2)\cdot 2^n} \cdot \begin{bmatrix} -(n - 3) \cdot 2^{n - 1} & 2^{n - 1} & \cdots & 2^{n - 1}\\ 2^{n - 2} & -(n - 3) \cdot 2^{n - 2} & \cdots & 2^{n - 2}\\ \vdots & \vdots & \ddots & \vdots \\ 1 & 1 & \cdots & -(n - 3) \end{bmatrix}

Precomputing this gives a good speedup as well.

My solution 
#include <bits/stdc++.h>
using namespace std;
#define int long long
 
int32_t main() {
    
    int t;
    cin >> t;
    
    int m[20][20] = {0};
    
    m[19][19] = -17;
    for (int i = 0; i < 19; ++i) {
        m[19][i] = 1;
    }
 
    for (int i = 18; ~i; --i) {
        for (int j = 0; j < 20; ++j) {
            m[i][j] = m[i + 1][(j + 1) % 20] * 2;
        }
    }
 
    int div = 18 << 20;
 
    while (t--) {
        int n;
        cin >> n;
        int s;
        vector<int> v(20);
        for (int i = 19; ~i; --i) {
            cout << 1 << " " << (1 << i) << endl;
            cin >> s;
            s -= (n << i);
            v[i] = s;
        }
        int ans = 0;
        for (int i = 0; i < 20; ++i) {
            int cur = 0;
            for (int j = 0; j < 20; ++j) {
                cur += m[i][j] * v[j];
            }
            cur /= div;
            ans += (cur & 1) << i;
        }
        cout << 2 << " " << ans << endl;
        cin >> s;
        assert(s == 1);
    }
    return 0;
}
4 Likes
3

Yes, I think Tester has also used some similar concept rather than explicitly carrying out Gaussian Elimination.

Thanks for the approach.

It would be helpful if you can provide a brief write-up which explains your solution. So that I can include that in the editorial.

1 Like
4

Here’s the write-up for explaining my solution.

Suppose the query is 1\,\,2^k for some k \in \{0, 1, \dots, 19\}. Then if the number of elements whose i^\mathrm{th} bit is on is x_k, then the difference between the answer of the query (say v_k) and the sum of all numbers would be (n - 2x_k) \cdot 2^k.

Note that the sum of all numbers is in fact \sum_{k = 0}^{19} x_k \cdot 2^k, so we have

v_k - n \cdot 2^k = x_0 \cdot 2^0 + \cdots + x_{k - 1} \cdot 2^{k - 1} - x_k \cdot 2^k + \cdots + x_n \cdot 2^n.

Treating this as a set of linear equations in x_i's, we write it as

\begin{bmatrix} -1 & 2 & \cdots & 2^{19}\\ 1 & -2 & \cdots & 2^{19}\\ \vdots & \vdots & \ddots & \vdots\\ 1 & 2 & \cdots & -2^{19} \end{bmatrix} \cdot \begin{bmatrix} x_0\\ x_1\\ \vdots\\ x_{19}\\ \end{bmatrix}= \begin{bmatrix} v_0 - n \cdot 2^0\\ v_1 - n \cdot 2^1\\ \vdots\\ v_{19} - n \cdot 2^{19} \end{bmatrix}

Now note that the inverse of the 20 \times 20 matrix is in fact

A = \dfrac{1}{18 \cdot 2^{20}} \cdot \begin{bmatrix} -17 \cdot 2^{19} & 2^{19} & \cdots & 2^{19} \\ 2^{18} & -17 \cdot 2^{18} & \cdots & 2^{18} \\ \vdots & \vdots & \ddots & \vdots \\ 1 & 1 & \cdots & -17\\ \end{bmatrix}

So our final result is

\begin{bmatrix} x_0\\ x_1\\ \vdots\\ x_{19}\\ \end{bmatrix}= A \cdot \begin{bmatrix} v_0 - n \cdot 2^0\\ v_1 - n \cdot 2^1\\ \vdots\\ v_{19} - n \cdot 2^{19} \end{bmatrix}

From the parity of x_k's, we can determine whether the bit in the final answer is 1 or not.

4 Likes
6

Check out Screencast Tutorial for this problem: https://www.youtube.com/watch?v=32I-KSuV6sA&list=PLz-fHCc6WaNJa2QJq7qULBBV0YOJunq75&index=5

7
8

Video Editorial for FINXOR - Find XOR (FINXOR) | Editorial | SEPT'20 Long Challenge | CodeChef | Competitive Programming - YouTube

3 Likes
9

Interesting, I didn’t use matrices at all or have to use gaussian elimination. Will post an explanation later but here is the code.

def ask_questions(n):
    print("1 1")
    k_zero = int(input())
    if k_zero == -1:
        raise Exception("cant ask with k == zero")
    last_digit = (n - k_zero) % 2
    reverse_digits = [last_digit]
    n_digits = 20
    for digit in range(1, n_digits):
        # ask question
        print(f"1 {((1<<n_digits)-1) - (1<<digit)  - 1}")
        # get the answer
        ans = int(input())
        x = k_zero + ans
        double_number_ones = x - n * (
            ((((1 << n_digits) - 1) ^ (1 << digit)))
        )
        reverse_digits.append(((double_number_ones >> (digit + 1))) & 1)
    ans = sum(reverse_digits[i] << i for i in range(len(reverse_digits)))
    print(f"2 {ans}")
    is_correct = int(input())
    if is_correct != 1:
        raise Exception("incorrect")


if __name__ == "__main__":
    T = int(input())
    for _ in range(T):
        N = int(input())
        ask_questions(N)
10

There is no. need of any matrix …it is just simple logic…i dont know why they used gaussian elemination like stuff…here is my code simple logic.Please explain the editorial in the most simplest way so that the users can understand and not fear the editorial

    #include <bits/stdc++.h>
    typedef long long ll;
    typedef unsigned long long ull;
    using namespace std;
    #define whatis(x) cout << #x << " is " << x << endl;

    //initialization of variable
    int numone[20];
    ull totalsum;
    ull xorsum[20];
    int n;

    void solve() {
        for (int i = 0; i < 20; i++) {
            ull k = (1 << i);
            ull tempsum = (totalsum + xorsum[i]);
            tempsum = tempsum - (n * k);
            tempsum = tempsum / 2;
            ull currentbitsum = totalsum - tempsum;
            currentbitsum = currentbitsum / k;
            numone[i] = currentbitsum;
        }
    }

    //Initializer function
    void init() {
        memset(numone, 0, sizeof(numone));
        memset(xorsum, 0, sizeof(xorsum));
        totalsum = 0;
        n = 0;
    }

    //Query function
    void query() {
        ull q = (1 << 20);
        cout << 1 << " " << q << endl;
        cin >> totalsum;
        totalsum = totalsum - (ull)(n*q);
        for (int i = 1; i < 20; i++) {
            q = (1 << i);
            cout << 1 << " " << q << endl;
            cin >> xorsum[i];
            if (xorsum[i] == (-1)) {
                exit(0);
            }
            cout.flush();
        }
    }`Preformatted text`

    //Function to print the ans
    void ans() {
        ull ans = 0;
        for (int i = 19; i > 0; i--) {
            if (numone[i] % 2 != 0) {
                ans = ans + (ull)(1 << i);
            }
        }
        totalsum = totalsum - ans;
        if(totalsum%2!=0){
            ans+=1;
        }
        cout << 2 << " " << ans << endl;
        cout.flush();
        int res;
        cin >> res;
        if (res == (-1)) {
            exit(0);
        }
    }
    int main() {
        ll test;
        cin >> test;
        while (test--) {
            init();

            cin >> n;
            //Initialization

            //Query for all the bits
            query();

            //Solve for the number of bits
            solve();

            //ans the sum
            ans();
        }
    }
7 Likes
11

yes used the same logic,observations can really simplify the solution

1 Like
12

yes…no need of any equation like stuff

2 Likes
13

Here’s another approach, i didn’t used matrix…

https://www.codechef.com/viewsolution/37690291

14

Actually, there’s one simple approach. Because of constraints of K, you can ask 20th power of 2 which is greater than 10^6 and less than 2* 10^6. and asking 2^20 will give you sum of all elements in the array.

After knowing the sum of all the elements of the array, now if you ask a question(only particular bit), lets say 64(2^6), then you can figure out the difference in value which is given by grader and the total sum and can find a pattern :slight_smile: .

link to my solution : CodeChef: Practical coding for everyone

4 Likes
15

This is the kind of editorial which might scare people. It is very nice and probably, the setter made the question with this approach in mind when a much simpler approach was available.

I used this logic:

First query 2^{20}, and store this sum as a reference point. Also, this tells us the parity of the first (least significant) bit. Notice that under the given constraints, none of the elements of the hidden numbers will have the 20^{th} bit occupied. So, if we subtract n*2^{20} from the input, the sum will be the same as obtained by querying for 0. Let the input for 2^{20} be A.

Now query 2^i \forall i \in [1, 19]. Notice that when you xor any number by 2^i, its i^{th} bit gets flipped.

Say there are n numbers with the i^{th} bit turned on and m numbers with the bit turned of. When you queried 2^{20}, the i^{th} bit contributed 2^i*n to the sum and when you query 2^i, it contributes 2^i * m to the sum while the contribution of the other bits does not change. Let the input for 2^i be B.

A-B = 2^i*(n- m)

Thus, n-m = \dfrac{A-B}{2^i}

Also, the total number of elements in the hidden array are n+m = N.

Then n = \dfrac{N + \dfrac{A-B}{2^i}}{2}

If the parity of set bits is odd, then the bit will be set in the final xor as well, else it will not be set.

Code 
for (int t = 0; t < tc; t++){
		int n;
		cin >> n;
		ll ans1 = 0;
		ll sum;
		cout << 1 << " " << 1048576 << endl;
		cin >> sum;
		sum -= n*1048576;
		if(sum%2) ans1 = 1;
		for(int i = 1; i <= 19; i++){
			cout << 1 << " " << (1 << i) << endl;
			ll sum1;
			cin >> sum1;
			ll diff = sum - sum1;
			diff = diff/(1LL << i);
			ll on = (n + diff)/2;
			if(on%2 == 1) ans1 |= (1 << i);
		}
		cout << 2 << " " << ans1 << endl;
		int j;
		cin >> j;
		assert(j == 1);
	}

In the code, N is denoted n, A by sum, B by sum1 and n by on

27 Likes
16

I’m surprised to see Gaussian eliminations and matrixes and stuff, it’s actually quite simple. The main observation/step is the following:
If we first query some X, and than query Y = (X ^ (1 << b)) (same as X, except on position b), we get:
All positions except b will be same everywhere, so their contribution to both sums will be the same.
So, if we subtract these 2 sums, we find 2^b * (ones(b) - zeroes(b)). On the other hand, ones(b) + zeroes(b) = n, meaning we uniquely find number of 1 bits on position b in numbers (A[i] XOR X). We can choose X so that it has all 0-s in positions 0,…,19.

I omitted a few small details, but here’s my solution - CodeChef: Practical coding for everyone.

1 Like
17

CAN SOMEBODY PLEASE HELP ME OUT WITH THIS. I DON’T UNDERSTAND SO AS TO WHAT IS WRONG IN MY LOGIC.
I WAS WAITING FOR 4 DAYS FOR THE CONTEST TO GET OVER AND I BE ABLE TO DISCUSS THE SOLUTION. GOT ANXIETY LEVEL PRO MAX XD

#i nclude < bits / stdc++.h >
using namespace std;

int main()
{
int t;
cin>>t;
long long int arr[22]={1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0};
for (int i=1;i<21;i++)
{
arr[i]=2*arr[i-1];
}
for(int z=t;z>0;z–)
{
int n;
cin>>n;
cout<<1<<" “<<arr[20];
int ans;
cin>>ans;
ans=ans-(arr[20]*n);
int func = 0;
if (ans%2!=0)
{
func=func+1;
}
for (int i=0;i<20;i++)
{
int ansu;
ansu=ans+(arr[i]*n);
cout<<1<<” “<<arr[i];
int tans;
cin>>tans;
if (((ansu-tans)/(arr[i]*2))%2 !=0)
{
func=func+arr[i];
}
}
cout<<2<<” "<<func<<endl;
int end;
cin>>end;
}
}

18

Here is my simple solution using python.

import sys
def readArr():
	return [int(x) for x in input().split()]

def ask(what):
	print(1,what,flush=True)
	reply = int(input())
	if reply == -1:
		sys.exit(1)
	return reply

def solve():
	N = int(input())
	k = 2**20 - 1
	sm = (N*k - ask(k)) #o+e=n
	ans = 0
	to_use = 0
	for i in range(19):
		n = 2**i;
		tmp = (ask(n) - sm)
		to_use += tmp
		tmp //= n
		ones = (N - tmp) // 2
		#print("tmp",tmp,"ones",ones)
		ans += n*(ones%2)
		#print("ans now",ans)
	#power 19
	mytmp = ((N*k - sm) - to_use - sm) // (2**19)
	ans += (((N-mytmp) // 2) % 2) * (2**19)

	print(2,ans,flush=True)
	flag = int(input())
	if flag == -1:
		sys.exit(1)

if __name__ == "__main__":
	# T = 1
	T = int(input())
	for t in range(T):
		solve()
1 Like
19

thats what is used there in my code

2 Likes
20

I think It Should be:
Lets, define x_{k} for 0<=k<=19, as the number of elements in array A with kth bit “OFF”.

Because if the 2^i th bit is OFF,then only it will contribute to q_{i}

@krikti
Can You Correct me?

21

No, the statement is correct.

Try to verify this by taking a small example. :slight_smile:

1 Like