PROBLEM LINK:
Setter: Soumyadeep Pal
Tester: Manan Grover
Editorialist: Ajit Sharma Kasturi
DIFFICULTY:
CAKEWALK
PREREQUISITES:
Greatest Common Divisor, Floor function
PROBLEM:
Given an array A of N integers, we can apply the following operation on A any number of times (possibly zero): Choose an index i where A_i \geq 1 and perform A_i = \lfloor \frac{A_i}{2} \rfloor.
We need to find the minimum number of operations required to make GCD(A_1, A_2 \dots A_N) odd.
QUICK EXPLANATION:
-
Let us first find the gcd of all the elements and store it in gcd.
-
In order to make gcd odd, we need to find the maximum value x for which gcd is divisible by 2^x and apply the operation x number of times on that element in the array which is divisble by 2^x but not 2^{x+1}.
-
Thus, x will be our final answer.
EXPLANATION:
-
For each element A_i in the array, let us calculate pow_i which is defined as follows: pow_i is the value such that A_i is divisible by 2^{pow_i} but not 2^{pow_i+1}. In other words, pow_i is the maximum power of 2 which divides A_i.
-
In order to make the gcd of all elements odd, it is enough that we make one of the elements odd. For that, we need to remove 2^{pow_i} from some element A_i by performing pow_i operations on it.
-
To minimize the number of operations, we need to select such an index i for which pow_i is minimum.
-
Thus, our final answer will be min(pow_1, pow_2, pow_3, \dots pow_N).
TIME COMPLEXITY:
O(N \log 10^9) for each testcase.
SOLUTION:
Editorialist's solution
#include <bits/stdc++.h>
using namespace std;
int main()
{
int tests;
cin >> tests;
while (tests--)
{
int n;
cin >> n;
vector<int> a(n);
for (int i = 0; i < n; i++)
cin >> a[i];
int gcd = a[0];
for (int i = 1; i < n; i++)
gcd = __gcd(gcd, a[i]);
int ans = 0;
while (gcd % 2 == 0)
{
gcd /= 2;
ans++;
}
cout << ans << endl;
}
}
Setter's solution
#include<bits/stdc++.h>
using namespace std;
void solve(int tc) {
int n; cin >> n;
int ans = 30;
for (int i = 0; i < n; i++) {
int x; cin >> x;
int cnt = 0;
while (x % 2 == 0) {
cnt++;
x /= 2;
}
ans = min(ans, cnt);
}
cout << ans << '\n';
}
signed main() {
ios_base :: sync_with_stdio(0); cin.tie(0); cout.tie(0);
int t = 1;
cin >> t;
for (int i = 1; i <= t; i++) solve(i);
return 0;
}
Tester's solution
#include <bits/stdc++.h>
using namespace std;
int main(){
ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
int t;
cin>>t;
while(t--){
int n;
cin>>n;
int ans = 100;
for(int i = 0; i < n; i++){
int temp;
cin>>temp;
int cnt = 0;
while(temp % 2 == 0){
temp /= 2;
cnt++;
}
ans = min(ans, cnt);
}
cout<<ans<<"\n";
}
return 0;
}
Please comment below if you have any questions, alternate solutions, or suggestions. 
