1198A. MP3 - Codeforces Solution C++

➤  Problem Link : 1198A. MP3 

✅ C++ Solution :

 
#include<bits/stdc++.h>
using namespace std;
 
#define ll long long int
 
int main()
{
  ll n,s;
  cin>>n>>s;
  ll arr[n+1];
  for(ll i=1;i<=n;i++)
    cin>>arr[i];
  sort(arr+1,arr+n+1);
  ll k;    
  ll low=0,high=n,mid;
  double val=(8*(double)s)/n;
  while(low<high)
  {
      mid=low+(high-low+1)/2;
      double d = log(mid)/log(2);
      if(ceil(d)<=val)
          low=mid;
      else
          high=mid-1;
  }
  k=high;
//  cout<<k<<endl;
      
      
  ll i=1,j=1;
  ll diff=1;
  ll ans=n;
  while(i<=n)
  {
    while(j<n)
    {
      
      if(j<n && arr[j+1]==arr[j])
        j++;
      if(j<n && arr[j+1]!=arr[j])
      {
        if(diff<k)
        {
          diff++;
          j++;
        }
        else
          break;
      }
    }
    ans=min(ans,i-1 + n-j);
    while(i<n && arr[i]==arr[i+1])
      i++;
    diff--;
    i++;
 
  }
  cout<<ans;
}

 

Thank you for your patience reading. If you enjoyed this post, I’d be very grateful if you’d help it spread by emailing it to a friend, or sharing it on Whatsapp or Facebook. 

😇Happy Learning!!

• Tweet
• Share
• Share
• Share
• Share

About Utkarsh Gupta

I am a Member Technical at D.E. Shaw India Pvt. Ltd. CodingWithArt is a blog where you find tricks and solutions to challenging coding and development problems. I aim to build a universal tech platform for every enthusiast out there.