 # BURSCRCK Editorial

Deepavali Code Battle

Author: Aayush Gupta
Tester: Tejus Kaw
Editorialist: Tejus Kaw

EASY

# PREREQUISITES:

Binary Numbers and its operations.

# PROBLEM:

Given N numbers in an array , you have to make all elements equal to zero by applying some operations. You have to select k then in each operation, select k distinct indexes,
X=a{i_1} \& a{i_2} \& … \& a_{i_k} and subtract X from each element.
Solve how many number of values of k and which values of k , will the solution be there for a given array.

# EXPLANATION:

Let’s note, that in one operation for any bit i (0 < i < 30) we either change all k^{th} non-zero bits into zero bits, or nothing changes.
So, the number of i^{th} non-zero bits in the array either decreases by k or doesn’t change. In the end, all these numbers will be equal to 0.
So, to be able to operate the array, the number of i^{th} non-zero bits In the array should be divisible by k for all bits i.

Let’s prove, that it is enough to make the array to zeroes. Let’s make operations with non-zero AND, while we can make them. In the end, there is at least one non-zero element, if we have not destructed the array. So, there Is at least one bit i, for which the number of i^{th} non-zero, bits In the array Is non-zero, so this number Is at least k (because it Is divisible by k). So we can select kt numbers with i^{th} non-zero bit to the next operation and make the new destruction, which is impossible.

So the resulting solution is: for each bit i (0 < i < 30) let’s find the number of array’s elements with non-zero e^{th} bit, Let’s find all
common divisors k (1 < k^t < n) of these numbers.

Time complexity is O(n log C), where C = 10° — upper limit on all numbers in the array.

# SOLUTIONS:

Setter's Solution
``````#include <bits/stdc++.h>
using namespace std;

void solve(){
int n;
cin >> n;
vector<int> freq(30);
for(int i = 0; i < n; i++){
int a;
cin >> a;
for(int j = 0; j < 30; j++){
if((1 << j) & a) freq[j]++;
}
}
int g = 0;
for(int x : freq){
g = gcd(g, x);
}
for(int i = 1; i <= n; i++){
if(g % i == 0){
cout << i << ' ';
}
}
cout << '\n';
}

int main(){
ios_base::sync_with_stdio(false), cin.tie(nullptr);
int T;
cin >> T;
while(T--) solve();
}
``````