کوکو کھانے کیلے لیٹ کوڈ حل


مشکل سطح درمیانہ
اکثر پوچھا جاتا ہے فیس بک
ثنائی تلاش

مسئلہ یہ بیان

"کوکو ایٹنگ کیلے" کی پریشانی میں ہمیں سائز ن کی ایک صف دی جاتی ہے جس میں ہر ڈھیر میں کیلے کی تعداد ہوتی ہے۔ ایک گھنٹے میں کوکو زیادہ تر کے کیلے کھا سکتے ہیں۔ اگر اس ڈھیر میں کے کیلے سے بھی کم مقدار موجود ہو اگر کوکو اس ڈھیر کے تمام کیلے ختم کردے تو وہ اسی گھڑی میں دوسرے ڈھیر سے کیلے کھانے کا آغاز نہیں کرسکتی ہے۔

کوکو H گھنٹے کے اندر تمام کیلے کھانا چاہتا ہے۔ ہمیں K کی کم سے کم قیمت ملنی ہے۔

مثال کے طور پر

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

وضاحت: 

کوکو کھانے کیلے کا لیٹکوڈ حل

کوکو 6 گھنٹے میں تمام کیلے کھانے کے ل ban اس طرح کیلے کھائیں گے:

پہلا گھنٹہ: 23

دوسرا گھنٹہ: 7

تیسرا گھنٹہ: 11

چوتھا گھنٹہ: 23

پانچویں گھنٹہ: 4

چھٹا گھنٹہ: 20

کوکو کھانے کے کیلے لیٹ کوڈ حل کے ل. اپروچ

اس مسئلے کو حل کرنے کے لئے سب سے پہلی اور سب سے اہم بات یہ ہے کہ مشاہدے سامنے لائیں۔ ہمارے تلاش کے وقفے کے لئے یہاں کچھ مشاہدات ہیں:

  1. کوکو کو فی گھنٹہ کم از کم ایک کیلا کھانا چاہئے۔ تو یہ K کی کم سے کم قیمت ہے آئیے اس کا نام رکھیں آغاز
  2. ہم ایک ڈھیر میں کیلے کی زیادہ سے زیادہ تعداد کو محدود کرسکتے ہیں جو تمام ڈھیروں میں سے ڈھیر میں کیلے کی زیادہ سے زیادہ تعداد تک لے جاسکتا ہے۔ تو یہ K کی زیادہ سے زیادہ قیمت ہے آئیے اسے نام دیں اختتام

اب ہمارے پاس اپنا وقفہ ہے۔ فرض کریں وقفہ کی جسامت ہے لمبائی اور ڈھیروں کی تعداد ہے n.  بولی نقطہ نظر وقفہ میں ہر قیمت کی جانچ کرنا ہوسکتا ہے۔ اگر کوکو کی اس قدر کے لئے H گھنٹے میں تمام کیلے کامیابی کے ساتھ کھا سکتے ہیں تو ان میں سے کم سے کم انتخاب کریں۔ بولی نقطہ نظر کے لئے وقت کی پیچیدگی بدترین حالت میں لمبائی * n ہوگی۔

ہم لکیری سرچ کی جگہ بائنری سرچ کا استعمال کرکے وقت کی پیچیدگی کو بہتر بنا سکتے ہیں۔

وقت کی پیچیدگی کا استعمال کرتے ہوئے ثنائی تلاش نقطہ نظر لاگ (لمبائی) * n ہو گا۔

عمل

کوکو کھانے کے کیلے کے لئے C ++ کوڈ

#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

کوکو کھانے کیلے لیٹ کوڈ حل کی پیچیدگی کا تجزیہ

وقت کی پیچیدگی

مذکورہ کوڈ کی ٹائم پیچیدگی ہے O (n * لاگ (W)) کیونکہ ہم ایک اور W کے مابین ثنائی کی تلاش کر رہے ہیں جس میں لاگ ڈبلیو وقت لگتا ہے اور ہر قیمت کے ل the ، بائنری تلاش میں ، ہم ڈھیروں کی صف کو عبور کررہے ہیں۔ تو ڈھیروں کا سرنی گزر جاتا ہے لاگ ڈبلیو میں وقت کی پیچیدگی کو ن * لاگ ڈبلیو بنا دیتا ہے۔ یہاں ن اور ڈبلیو ڈھیر کی تعداد اور ڈھیر میں کیلے کی زیادہ سے زیادہ تعداد ہیں۔

خلائی پیچیدگی

مذکورہ کوڈ کی جگہ کی پیچیدگی ہے O (1) کیونکہ ہم جواب کو ذخیرہ کرنے کے لئے صرف متغیر کا استعمال کررہے ہیں۔

حوالہ جات