PROBLEM LINK:
Author: Onkar Ratnaparkhi
Tester: MPS Prasanth
Editorialist: Onkar Ratnaparkhi
DIFFICULTY:
EASY
PREREQUISITES:
Bitwise XOR operator
PROBLEM:
You are given an array of N positive integers. All its elements are guaranteed to be powers of 2. In one operation, you can select an index and divide the element on that position by 2.
Find the minimum number of operations required to make the Bitwise XOR of all the elements 0.
QUICK EXPLANATION:
Calculate the XOR of all the elements. And traverse the result from MSB to LSB. If there is a 1 on i^{th} position, apply an operation and move it to next position (cnt++). If there is 1 already present in the next position, it will get canceled. At the end of traversal, you will have your solution.
EXPLANATION:
We know that
X XOR X = 0
X XOR 0 = X
Let’s calculate xor of all the elements in the array, let’s call it X.
Let’s traverse the binary representation of X from MSB to LSB.
If there is a 1 on i^{th} position, it means there is a 2^i present in the array on which we need to apply the operation and convert it to 2^{i-1} thereby increasing the operation’s count by 1.
Applying the operation on that 2^{i} is same as:
- Shifting the 1 at i^{th} position in X to next position
- Now, if next position does not exist, it’s well and good. We are done here.
- If it exists and there is a 1 present, they will cancel each other i.e. next position will become 0.
- else if there is a 0 on the next position, it will become 1.
At the end of traversal, you will have the required count.
Time Complexity
O(n)
SOLUTIONS:
Setter's Solution
#include <bits/stdc++.h>
using namespace std;
#define ll long long
int main() {
// freopen(input, "r", stdin);
// freopen(output, "w", stdout);
ll t;
cin>>t;
assert(t>=0 and t<=10000);
while(t--){
int n;
cin>>n;
assert(n>0 and n<=100000);
vector<int> ar(n);
for(int i=0;i<n;i++){
cin>>ar[i];
assert(ar[i]>0 and ar[i]<(1ll<<20));
}
vector<int> v(21);
for(auto it:ar){
int cnt=0;
while(it){
cnt++;
it/=2;
}
v[cnt-1]++;
}
int ans=0, cnt=0;
for(int i=20;i>=0;i--){
if(cnt){
v[i]++;
cnt=0;
}
if(v[i]&1){
cnt=1;
ans++;
}
}
cout<<ans<<endl;
}
}
Tester's Solution
#include <bits/stdc++.h>
using namespace std;
int main()
{
int t;
cin >> t;
while (t--)
{
int n;
cin >> n;
vector<int> v(n);
for (int i = 0; i < n; i++)
{
cin >> v[i];
}
sort(v.begin(), v.end());
int ans = 0, count = 1;
for (int i = n - 1; i > 0; i--)
{
if (v[i] == v[i - 1])
{
count++;
}
else
{
if (count % 2 != 0)
{
while (v[i] != v[i - 1])
{
v[i] /= 2;
ans++;
}
count = 2;
}
else
{
count = 1;
}
}
}
if (count % 2 == 1)
{
int c = 0;
while (v[0] > 0)
{
c++;
v[0] = v[0] / 2;
}
ans += c;
}
cout << ans << endl;
}
return 0;
}
Editorialist's Solution
#include<bits/stdc++.h>
using namespace std;
void solve(){
cin>>n;
vll ar(n);
cin>>ar;
int x=0;
for(auto it:ar)
x ^= it;
int cnt=0;
for(int i=20;i>=0;i--){
if(x&(1ll<<i)){
cnt++;
x^=(1ll<<i);
if(i>0)
x^=(1ll<<(i-1));
}
}
cout<<cnt<<endl;
}
int main(){
int t;
cin>>t;
while(t--){
solve();
}
return 0;
}