BURSCRCK Editorial

editorial
1

PROBLEM LINK:

Deepavali Code Battle

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

DIFFICULTY:

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();
}