কোকো খাওয়া কলা লেটকোড সমাধান


কাঠিন্য মাত্রা মধ্যম
প্রায়শই জিজ্ঞাসা করা হয় ফেসবুক
বাইনারি অনুসন্ধান

সমস্যা বিবৃতি

"কোকো খাওয়া কলা" সমস্যাটিতে আমাদের আকারের এন অ্যারে দেওয়া হয় যা প্রতিটি স্তূপে কলা সংখ্যা ধারণ করে। এক ঘন্টার মধ্যে কোকো বেশিরভাগ কে কলা খেতে পারেন। যদি সেই স্তূপে কে-কলা কম থাকে তবে কোকো যদি সেই স্তূপের সমস্ত কলা শেষ করে দেয় তবে সে একই ঘন্টার মধ্যে অন্য গাদা থেকে কলা খেতে শুরু করতে পারে না।

কোকো এইচ ঘন্টার মধ্যে সমস্ত কলা খেতে চায়। আমাদের কে এর সর্বনিম্ন মান খুঁজে পাওয়ার কথা রয়েছে are

উদাহরণ

piles = [30,11,23,4,20], H = 6
23

ব্যাখ্যা: 

কলা খাওয়ার কোকোতে লেটকোড দ্রবণ

কোকো এইভাবে 6 ঘন্টা সমস্ত কলা খেতে কলা খেতে হবে:

প্রথম ঘন্টা: 23

দ্বিতীয় ঘন্টা: 7

তৃতীয় ঘন্টা: 11

চতুর্থ ঘন্টা: 23

পঞ্চম ঘন্টা: 4

ষষ্ঠ ঘন্টা: 20

কোকো খাওয়ার কলা লেটকোড সলিউশন এর পদ্ধতির

এই সমস্যাটি সমাধান করার জন্য প্রথম এবং সবচেয়ে গুরুত্বপূর্ণ জিনিসটি পর্যবেক্ষণগুলি আনা। আমাদের অনুসন্ধানের ব্যবধানের জন্য এখানে কয়েকটি পর্যবেক্ষণ রয়েছে:

  1. কোকোকে অবশ্যই প্রতি ঘন্টায় কমপক্ষে একটি কলা খেতে হবে। সুতরাং এটি কে এর সর্বনিম্ন মান let's শুরু
  2. আমরা কোকো এক ঘন্টার মধ্যে সর্বাধিক সংখ্যক কলা খেতে পারি, সমস্ত গাদা থেকে বের করে একটি গাদাতে সর্বাধিক কলা সীমাবদ্ধ করতে পারি। সুতরাং এটি কে-এর সর্বাধিক মান শেষ।

এখন আমাদের অনুসন্ধানের ব্যবধান রয়েছে। ধরা যাক অন্তরালের আকার লম্বা এবং গাদা সংখ্যা হয় n.  নিষ্পাপ পদ্ধতির অন্তর অন্তর প্রতিটি মান পরীক্ষা করা যেতে পারে। যদি K মানকটির এই মানটির জন্য H ঘন্টা সাফল্যের সাথে সমস্ত কলা খেতে পারে তবে সেগুলির মধ্যে সর্বনিম্ন চয়ন করুন। নিষ্পাপ পদ্ধতির জন্য সময় জটিলতা সবচেয়ে খারাপ ক্ষেত্রে দৈর্ঘ্য * n হবে।

লিনিয়ার সন্ধানের জায়গায় বাইনারি অনুসন্ধান ব্যবহার করে আমরা সময়ের জটিলতা উন্নত করতে পারি।

সময় জটিলতা ব্যবহার করে বাইনারি অনুসন্ধান পদ্ধতির লগ হবে (দৈর্ঘ্য) * এন।

বাস্তবায়ন

কোকো খাওয়ার কলা জন্য সি ++ কোড

#include <bits/stdc++.h>
using namespace std; 
       int minEatingSpeed(vector<int>& pile, int hour) {
        int left = 1, right = *max_element(pile.begin(),pile.end());;
        while (left < right) {
            int mid = (left + right) / 2, total = 0;
            for (int p : pile) total += (p + mid - 1) / mid;
            if (total > hour) left = mid + 1; else right = mid;
        }
        return left;
    }
int main() 
{ 
 vector<int> arr = {30,11,23,4,20}; 
 int H=6;                               
 cout<<minEatingSpeed(arr,H)<<endl;
 return 0;
}
23

কোকো খাওয়ার কলা জন্য জাভা কোড

import java.util.Arrays; 
public class Tutorialcup {
    public static int minEatingSpeed(int[] piles, int H) {
        int left = 1, right =Arrays.stream(piles).max().getAsInt();
        while (left < right) {
            int mid = (left + right) / 2, total = 0;
            for (int p : piles) total += (p + mid - 1) / mid;
            if (total > H) left = mid + 1; else right = mid;
        }
        return left;
    }
  public static void main(String[] args) {
    int [] arr = {30,11,23,4,20}; 
     int H=6; 
    int ans= minEatingSpeed(arr,H);
    System.out.println(ans);
  }
}
23

কোকো খাওয়ার কলা লেটকোড সমাধানের জটিলতা বিশ্লেষণ

সময়ের জটিলতা

উপরের কোডটির সময় জটিলতা ও (এন * লগ (ডাব্লু)) যেহেতু আমরা এক এবং ডব্লু এর মধ্যে বাইনারি অনুসন্ধান করছি এটি লগডাব্লু সময় লাগে এবং প্রতিটি মানের জন্য বাইনারি অনুসন্ধানে আমরা পাইলস অ্যারেটি অনুসরণ করি। সুতরাং পাইলস অ্যারে লগডাব্লু বারগুলিকে বিভ্রান্ত করে এটি সময়কে জটিল করে তোলে * লগডাব্লু। এখানে এন এবং ডব্লু হ'ল পাইলসের সংখ্যা এবং একটি গাদাতে সর্বাধিক কলা সোনার সংখ্যা।

স্থান জটিলতা

উপরের কোডটির স্পেস জটিলতা ও (1) কারণ আমরা উত্তর সংরক্ষণের জন্য কেবল একটি পরিবর্তনশীল ব্যবহার করছি।

তথ্যসূত্র