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.
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 
I did some testing. Surprisingly, this is not the case because of the floor function.
1 Like
Can you explain you approach ?