K3HLPSM-Editorial

editorial
,
1

PROBLEM LINK:

Practice
Contest Link

Author: Lakshay Kumar
Editorialist: Anugya Jain

DIFFICULTY:

EASY-MEDIUM

PREREQUISITES:

Math,Map or Hash,Array

PROBLEM:

Sam has an array A of length N.In one operation you can select an index i(1≤i≤N) and change A[i] to floor(A[i]/2) .You have to make all the elements equal. Calculate the minimum number of operations needed to do so.

EXPLANATION:

Try to think what element will each index have at the end.
Since we want the minimum number of operations, we want to give the maximum number to each element.

So, we need to find the maximum value each index can attain.

We can do this by iterating over all possibilities of an element at an index and maintain overall frequency.

We can then maximum element with frequency N.

Each element has only log(A[i]) possibilities. So the overall complexity is O(N log(A[i]))

SOLUTIONS:

Editorialist's Solution 
#include<bits/stdc++.h>
using namespace std;
int solve(vector<int>&v)
{
    int n=v.size();
    unordered_map<int,int>m;
    for(int i=0;i<n;i++)
    {
        int temp=v[i];
        while(temp>1)
        {
            temp/=2;
            m[temp]+=1;
        }
        m[v[i]]+=1;
    }
    int mx=0;
    for(auto it:m)
    {
        int temp=it.second;
        if(temp==n)
        {
            mx=max(mx,it.first);
        }
    }
    int ans=0;
    // cout<<mx;
    for(int i=0;i<n;i++)
    {
        int temp=v[i];
        while(temp!=mx)
        {
            ans+=1;
            temp/=2;
        }
    }
    return ans;
}
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int n;
    cin>>n;
    vector<int>v(n,0);
    for(int i=0;i<n;i++)
    {
        cin>>v[i];
    }
    cout<<solve(v);
}