Help needed in array problem

Given an array of N integers. We need to make all the elements of the array equal.
In one operation we can divide or multiply an element by 2. We need to find minimum no of operations to make all the elements of the array equal

2 Likes

can you give problem link and some test cases

1 Like

I dont have a link to that problem.
For ex consider the case of 3 numbers
2 4 6
the answer is 4

How exactly, Is it \lceil x/2 \rceil?

1 Like

It is floor divison

010
100
110

010
010
110

010
010
011

010
010
001

010
010
010

I guess you can find the gcd of all the elements, divide all the elements by the gcd.
Then for the elements that aren’t a power of 2, add the least division required to make it a power of 2 to the ans, and change it to the power of 2. Then find the optimal power of 2, by finding the \sum abs(log_2 a[i] - idx) over all i. This can be done in O(nlog n) or O(nlog(log(n))) depending on how much effort you’re willing to do.

1 Like

can you explain a little bit simpler

can you tell why are we dividing by gcd

If you want it in binary, find the bit representations of the smallest number. iterate through all the possible substrings and check whether they are present in the other numbers. For each substring that is present in all the other find the minimum change required to get them in the same place. This can be done in O(nlog^{2} n * log^2 a)

didnt understand maybe a bit simpler

I think it should be prefixes rather than substrings

Right, I guess I’m just being stupid right now, I’ll spend some time on testing.

Similar problem: https://codeforces.com/contest/1213/problem/D2

what you told about gcd how did you think it.

yeah but this problem has some variation may be the answer will be smaller than the original problem

ga,gb,gc…gz…

say g is the gcd. You can see that it wont hurt if you just divide my g, problem stays the same. All the values in the final array will be different by a factor of g.

#include <iostream>
#include <bits/stdc++.h>
#include <cmath>
#include <vector>
#define ll long long int
#define mp make_pair
#define pb push_back
#define vi vector<int>
using namespace std;
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
	int t;
	cin >>t;
	while(t--){
	    int n;
	    ll ans=0;
	    int mxcnt=0; //stores the largest binary length
	    cin>>n;
	    ll a[n];
	    string bin[n]; //  stores binary representation as a string
	    for(int i=0;i<n;i++){
	        cin>>a[i];
	        ll x=a[i];
	        bin[i]="";
	        int cnt=0; //will store length of a[i] in binary
	        while(x){
	            cnt++;
	            if(x%2){
	                bin[i]+='1';
	            }
	            else{
	                bin[i]+='0';
	            }
	            x/=2;
	        }
	        ans+=cnt; // the answer if all were to be made 0.
	        mxcnt=max(cnt,mxcnt); 
	         reverse(bin[i].begin(), bin[i].end()); //reversing to store in the correct order 
	    }
	    tuple<string,ll,ll> prefixes[n][mxcnt+5]; //prefix, initial position, operation needed to reach. Index: element, size 
	    for(int i=0;i<n;i++){
	        for(int j=0;j<mxcnt+5;j++){
	            prefixes[i][j]=make_tuple("",1e9,0); //making sure we don't use an incorrect prefix
	        }
	    }
	    for(int i=0;i<n;i++){ //finding the values of prefixes for each element.
	       string currprefix="";
	       for(int j=0;j<bin[i].size();j++){
	           currprefix+=bin[i][j];
	           for(int k=j+1;k<bin[i].size();k++){
	              if(bin[i][k]=='1'){
	                  get<0>(prefixes[i][j+1])=currprefix;
	                  get<2>(prefixes[i][j+1])=bin[i].size()-k;
	                  get<1>(prefixes[i][j+1])=k-j-1;
                  break;
	              }
	           }
	           if(get<1>(prefixes[i][j+1])==1e9){
	               get<0>(prefixes[i][j+1])=currprefix;
	               get<2>(prefixes[i][j+1])=0;
	               get<1>(prefixes[i][j+1])=bin[i].size()-j-1;
	           }
	       }
	        
	    }
	    for(int i=1;i<=bin[0].size();i++){
	        ll checkans=0; //ans for this prefix
	        ll minop=1e12; // minimum operation needed to get them to the same.
	        bool poss=1;
	        string currprefix=get<0>(prefixes[0][i]);
            cheackans+=get<2>(prefixes[0][i]);
	        for(int j=1;j<n;j++){
	            if(get<0>(prefixes[j][i])!=currprefix){
	                poss=0;
	                break;
	            }
	            checkans+=get<2>(prefixes[j][i]);//operation to actually use this prefix
	        }
	        if(poss){
	            ll checkans2=0; // for j 0s
	            for(int j=0;j<=mxcnt;j++){
	                for(int k=0;k<n;k++){
	                    checkans2+=abs(get<1>(prefixes[k][i])-j); 
	                }
	                minop=min(minop,checkans2);//finds the minimum operation after making the prefixes usable.
                    checkans2=0;
	            }
                checkans+=minop;
                ans=min(ans,checkans);
	        }
	    }
	    cout<<ans<<"\n";
	    }
	}

complexity=O(nlog^2(max(a[i])))
I guess my brain only works while coding :sweat_smile:

I did some testing. Surprisingly, this is not the case because of the floor function.

1 Like

Can you explain you approach ?