REC25B - Editorial

Contest
Author: kushal
Testers: pra1shukla, chef_ash
Editorialist: chef_ash

DIFFICULTY:

CAKEWALK

PREREQUISITES:

Bitwise AND

PROBLEM:

Given an array of numbers, you can do either of 2 operations any number of times, until the bitwise AND of all the elements of the array is non-zero.

  1. Divide all the numbers by 2
  2. Add 1 to any even number.

EXPLANATION:

If the bitwise AND of all the elements in the array is already non-zero, 0 is our answer since we need not do any operation. However, if it is not the case, we need to find minimum number of operations to make bitwise AND non zero. A simple way of looking at the problem is if we write all the numbers in their binary form, we need to find k, such that the count of numbers with their k^{th} bit set in their binary form is maximum. This way, we can minimize the number of times we do operation 1.

To ensure minimum number of total operations, we start checking from the rightmost set of bits such that we do minimum number of operation 2, i.e. we perform minimum number of right shifts.

The problem allows the brute force approach to pass so you can check for each of the 40 bits for each of these n numbers. Why 40? Since A_{i} can have a maximum value of 1e12 so the maximum length of the binary form can be log2(1e12)=40. The answer can be determined by the relation ans=min(ans, count+i) where i denotes the i^{th} set of bits from the right, i.e. operation number 2 has been performed i times and count denotes number of non set bits in the i^{th} set, i.e. number of times operation 1 needs to be performed.

SOLUTIONS:

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

int main() {
	// your code goes here
	ll t;
	cin>>t;
	while(t--){
	    ll n;
	    cin>>n;
	    vector<ll>V(n),A(n);
	    for(ll i = 0; i<n; i++){
	        cin>>V[i];
	        A[i] = V[i];
	    }
	    ll ans = INT_MAX;
	    for(ll j = 1; j<=40; j++){
	        ll ct = 0;
	        for(ll i = 0; i<n; i++){
	            if(A[i]%2==0){
	                ct++;
	            }
	            A[i] = A[i]/2;
	        }
	        if(ct==0){
	            ans = min(ct,ans);
	        }
	    }
	    for(ll j = 1; j<=40; j++){
	        ll ct = 0; 
	    for(ll i = 0; i<n; i++){
	        if(V[i]%2==0){
	            ct++;
	        }
	        V[i] = V[i]/2;
	    }
	    ct = ct+j-1;
	    ans = min(ans,ct);
	    }
	    cout<<ans<<endl;
	}
	return 0;
}
Tester's Solution
def solve(t):
    n = int(input().strip())
    lst = list(map(int, input().split()))  
    assert(len(lst)==n)
    ans = 9e18
    ab = lst[0]
    for i in range(1,n):
        ab = ab&lst[i]
    if(ab>0):
        ans=0
    else:
        for i in range(0,40):
            count = 0
            for j in range(0,n):
                if((lst[j] & 1)==0):
                    count+=1
                lst[j] = lst[j]>>1
            ans = min(ans,count+i)
    print(ans)

def main():
    tc = int(input().strip())
    for t in range(1,tc+1):
        (solve(t))

if __name__=="__main__":
    main()