BININVER - Editorial

PROBLEM LINK:

Practice
Div1
Div2
Div3

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. :slight_smile:

2 Likes

My Approach

My approach :
Find GCD of all elements of array.
Perform given operation for each element until gcd(a[i],gcd_of_array) > 1.
Find minimum steps wrt to each element. This is our answer

#include<bits/stdc++.h> 
#include<ext/pb_ds/assoc_container.hpp>
#include<ext/pb_ds/tree_policy.hpp>
#define ll long long 
#pragma GCC optimize("Ofast")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,avx2,fma")
#pragma GCC optimize("unroll-loops")
const unsigned int M = 1000000007;
using namespace std;
using namespace __gnu_pbds;
typedef tree<int,null_type,less<int>,rb_tree_tag,tree_order_statistics_node_update> T_set; // PBDS_set
typedef tree<int,null_type,less_equal<int>,rb_tree_tag,tree_order_statistics_node_update> T_multiset; // PBDS_multiset

void solve()
{
    int t, n;
    cin>>t;
    while(t--){
        cin>>n;
        vector<ll> x(n);
        for(ll &elem : x)
        cin>>elem;
        ll gcd = x[0];
        for(ll i = 1;i < n ; i++ )
        gcd = __gcd(x[0],x[1]);
        if(gcd == 1){
            cout<<"0\n";
        }else{
            int ans = INT_MAX;
            for(int i = 0; i < n ; i++ ){
                int temp = 0;
                while(__gcd(x[i],gcd) > 1)
                x[i]/=2,temp ++;
                ans = min(temp,ans);

            }
            cout<<ans<<"\n";
        }
    }
}
int main()
{
ios_base::sync_with_stdio(false);
cout.tie(NULL);
cin.tie(NULL);
solve();
return 0;
}


import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int t = scanner.nextInt();
        StringBuilder str = new StringBuilder();
        while (t-- > 0) {
            int n = scanner.nextInt();
            int[] arr = new int[n];
            for (int i = 0; i < n; i++) {
                arr[i] = scanner.nextInt();
            }
            boolean flag = false;
            int min = Integer.MAX_VALUE;
            for (int i = 0; i < n; i++) {
                arr[i] = countTrailingZero(arr[i]);
                min = Math.min(arr[i], min);
                if (arr[i] == 0) {
                    flag = true;
                    break;
                }
            }
            if (flag) {
                str.append("0").append("\n");
            } else {
                str.append(min).append("\n");
            }
        }
        System.out.println(str);
    }

    static int countTrailingZero(int x) {
        int[] lookup = {32, 0, 1, 26, 2, 23, 27, 0, 3, 16, 24, 30, 28, 11, 0, 13, 4, 7, 17, 0, 25, 22, 31, 15, 29, 10, 12, 6, 0, 21, 14, 9, 5, 20, 8, 19, 18};
        return lookup[(-x & x) % 37];
    }
}

Idea:
Count trailing zero bits using lookup table - GeeksforGeeks.

Once a number in array is odd, its GCD will be odd, so I just found the number with least number of trailing zeros in its binary representation, and printed that.

My solution:
Observation 1: if there is one even and one odd element is present in the array answer is always 0.
Observation 2: if there is no even element answer is always 1.
Observation 3: (element%4==2) answer is 1.
Observation 4: (element%4==0) we need to find step by step

Link : https://www.codechef.com/viewsolution/51851383

My Code fails for the test case

3
3 9 27

But it got accepted there :expressionless:

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

My Code using bits and an optimized approach

#include<bits/stdc++.h>
#define int long long
#define w(x) int x; cin>>x; while(x--)
int mod = (int)1e9+7;
#define maxv 9223372036854775807
#define minv -9223372036854775808
#define  add push_back
#define MAX (int)1e7+7
using namespace std;
void solve()
{
    int n;
    cin>>n;
    int a[n];
    for(int i=0;i<n;i++)
    {
        cin>>a[i];
    }
    int ans=maxv;
    for(int i=0;i<n;i++)
    {
        for(int j=0;j<32;j++)
        {
            if((a[i]>>j)&1)
            {
                ans=min(ans,j);
                break;
            }
        }
    }
    cout<<ans<<"\n";
}
int32_t main()
{
    #ifndef ONLINE_JUDGE
    freopen("Input.txt", "r", stdin);
    freopen("Output.txt", "w", stdout);
#endif
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int t;
    cin >> t;
    while (t--)
    {
        solve();
    }
}

can you tell what is logic behind the line I just found the number with least number of trailing zeros in its binary representation, and printed that.

My solution (With details)
https://www.codechef.com/viewsolution/51860617

The idea is:
1)GCD of odd and odd is odd, odd and even is odd, even and even is even.
2)If there is at least one odd, answer is 0. If there are even not divisible by 4 (a[i] %4 != 0) , then we can make them odd by dividing with 2. So, answer is 1.
3)Lastly, for even divisble by 4. we need to calculate steps to make them odd. Then the minimum steps will be the answer.

1 Like

When we divide a number by 2, a zero is removed from its binary repesentation. So we divide it by 2 till we reach 1 in its least significant bit(then it is not divisible by 2, which means odd). Once we reach odd, gcd becomes odd. So to make a number odd in minimum number of moves, find the trailling zeros(min) in binary representation of every number. Once we get that, we can divide that number that(no. of trailling zeros) many times by 2, to make gcd odd.

1 Like

I thought that if array consists of at least one odd element it’s gcd will already be odd?? If it doesn’t have any make any number odd by dividing by 2. some numbers take 1 some 2 operations to become odd by dividing by 2. It’ll be our answer. Is this approach right?? Where it might fail?? I tried but didn’t pass.

Yes, this approach is correct (a bit expensive, but should get accepted)

Approach:

  1. scan the array → if any number is odd → answer = 0
  1. if all numbers are even → divide each number with 2 until it becomes odd and keep a track of that count for each number → return the minimum count.

It would look something like this:

int main(){
    int t;
    cin>>t;
    while(t--){
        int n;
        cin>>n;
        int arr[n];
        for(int i=0;i<n;i++){
            cin>>arr[i];
        }

        int ans = INT_MAX;
        int done= 0;
        for(int i=0;i<n;i++){
            if(arr[i]%2==1){
                cout<<0<<endl;
                done=1;
                break;
            }
        }

        if(done==0){
            for(int i=0;i<n;i++){
                int res=0;
                while(arr[i]%2==0){
                    arr[i] /= 2;
                    res++;
                }
                ans = min(ans,res);
            }
            cout<<ans<<endl;
        }     
    }
    return 0;
}
1 Like

Is it possible to this problem in O(N) or O(Nlog10^9) is the only approach?

In Question, we are required to make GCD of the array to an odd integer, GCD of the array is even only if all the array elements are even, else odd in all other cases, To make GCD of the array as odd
there must exist at least one odd number since GCD(odd, even) = 1
so we are required to make at least a single number to odd if none of the array elements are odd,
so since we are allowed to do only one operation that is divide / 2
we need to find minimum operations that we need to divide each number by 2 so that number becomes odd. In Other Words, we need to find the minimum of the nearest set bit of each
number
For example:
consider array [4, 12, 24];
4 - 00100
12- 01100
24- 11000
to make 4 as odd we need to move 3 rd bit to 1st bit (2 moves)
to make 12 as odd we need to move 3rd bit to 1st bit (2 moves)
to make 24 as odd we need to move 4th bit to 1st bit(3 moves)

1 Like