कोको खाणे केळी लीटकोड सोल्यूशन


अडचण पातळी मध्यम
वारंवार विचारले फेसबुक
बायनरी शोध

समस्या विधान

“कोको खाणे केळी” या समस्येमध्ये आम्हाला आकाराचे एनरे दिले जाते ज्यामध्ये प्रत्येक ब्लॉकमध्ये केळीची संख्या असते. एका तासामध्ये कोको बहुतेक के केळी खाऊ शकतो. जर त्या ब्लॉकमध्ये के केळीपेक्षा कमी असेल तर कोकोने त्या ब्लॉकलाच्या सर्व केळ्या संपविल्या तर त्याच तासात ती दुस p्या ब्लॉकलामधून केळी खायला सुरू करू शकत नाही.

कोकोला एच के तासात सर्व केळी खाण्याची इच्छा आहे. आम्हाला के चे किमान मूल्य शोधले पाहिजे.

उदाहरण

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

स्पष्टीकरण: 

कोको खाणे केळीचे लीटकोड सोल्यूशन

कोको 6 तासांत सर्व केळी खाण्यासाठी अशा प्रकारे केळी खाईल:

पहिला तास: 23

दुसरा तास: 7

तिसरा तास: 11

चौथा तास: 23

पाचवा तास: 4

सहावा तास: 20

कोको एटींग केळी लीटकोड सोल्यूशनसाठी दृष्टीकोन

ही समस्या सोडवण्याची पहिली आणि सर्वात महत्वाची बाब म्हणजे निरीक्षणे आणणे. आमच्या शोध अंतरासाठी काही निरीक्षणे येथे आहेत.

  1. कोकोने तासाला किमान एक केळी खायलाच हवी. तर हे के. चे किमान मूल्य आहे प्रारंभ करा
  2. कोक एका तासात खाऊ शकणार्‍या केळीची जास्तीत जास्त संख्या आम्ही सर्व ब्लॉकलामधून ब्लॉकमध्ये घालू शकतो. तर हे के. चे अधिकतम मूल्य आहे समाप्त

आता आमचा शोध मध्यांतर आहे. समजा अंतराचा आकार आहे लांबी आणि मूळव्याधांची संख्या आहे n.  मध्यांतरातील दृष्टीकोन म्हणजे मध्यांतरातील प्रत्येक मूल्य तपासणे. जर कोक of्याच्या त्या मूल्यासाठी हरभजन तासात सर्व केळी खाऊ शकतील तर त्यातील किमान निवडा. निष्पाप पध्दतीसाठीची अवघडपणा सर्वात वाईट परिस्थितीत लांबी * एन असेल.

रेखीय शोधाच्या जागी बायनरी सर्चचा वापर करून आम्ही वेळेची जटिलता सुधारू शकतो.

वापरून वेळ गुंतागुंत बायनरी शोध दृष्टीकोन लॉग (लांबी) * एन असेल.

अंमलबजावणी

कोको खाण्याच्या केळीसाठी सी ++ कोड

#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) कारण आम्ही उत्तर संग्रहित करण्यासाठी फक्त एक व्हेरिएबल वापरत आहोत.

संदर्भ