ಕೊಕೊ ತಿನ್ನುವ ಬಾಳೆಹಣ್ಣು ಲೀಟ್‌ಕೋಡ್ ಪರಿಹಾರ


ತೊಂದರೆ ಮಟ್ಟ ಮಧ್ಯಮ
ಆಗಾಗ್ಗೆ ಕೇಳಲಾಗುತ್ತದೆ ಫೇಸ್ಬುಕ್
ಬೈನರಿ ಹುಡುಕಾಟ

ಸಮಸ್ಯೆ ಹೇಳಿಕೆ

”ಕೊಕೊ ತಿನ್ನುವ ಬಾಳೆಹಣ್ಣುಗಳು” ಸಮಸ್ಯೆಯಲ್ಲಿ ನಮಗೆ ಗಾತ್ರ n ನ ಒಂದು ಶ್ರೇಣಿಯನ್ನು ನೀಡಲಾಗುತ್ತದೆ, ಅದು ಪ್ರತಿ ರಾಶಿಯಲ್ಲಿ ಬಾಳೆಹಣ್ಣುಗಳ ಸಂಖ್ಯೆಯನ್ನು ಹೊಂದಿರುತ್ತದೆ. ಒಂದು ಗಂಟೆಯಲ್ಲಿ ಕೊಕೊ ಹೆಚ್ಚಿನ ಕೆ ಬಾಳೆಹಣ್ಣುಗಳನ್ನು ತಿನ್ನಬಹುದು. ಆ ಸಂದರ್ಭದಲ್ಲಿ ರಾಶಿಯಲ್ಲಿ ಕೆ ಬಾಳೆಹಣ್ಣುಗಳಿಗಿಂತ ಕಡಿಮೆ ಇದ್ದರೆ, ಕೊಕೊ ಆ ರಾಶಿಯ ಎಲ್ಲಾ ಬಾಳೆಹಣ್ಣುಗಳನ್ನು ಮುಗಿಸಿದರೆ, ಅದೇ ಗಂಟೆಯಲ್ಲಿ ಅವಳು ಇನ್ನೊಂದು ರಾಶಿಯಿಂದ ಬಾಳೆಹಣ್ಣುಗಳನ್ನು ತಿನ್ನಲು ಪ್ರಾರಂಭಿಸುವುದಿಲ್ಲ.

ಕೊಕೊ ಎಲ್ಲಾ ಬಾಳೆಹಣ್ಣುಗಳನ್ನು ಎಚ್ ಗಂಟೆಗಳಲ್ಲಿ ತಿನ್ನಲು ಬಯಸುತ್ತಾರೆ. ನಾವು ಕೆ ಯ ಕನಿಷ್ಠ ಮೌಲ್ಯವನ್ನು ಕಂಡುಹಿಡಿಯಬೇಕಾಗಿದೆ.

ಉದಾಹರಣೆ

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

ವಿವರಣೆ: 

ಕೊಕೊ ತಿನ್ನುವ ಬಾಳೆಹಣ್ಣಿಗೆ ಲೀಟ್‌ಕೋಡ್ ಪರಿಹಾರ

6 ಗಂಟೆಗಳಲ್ಲಿ ಎಲ್ಲಾ ಬಾಳೆಹಣ್ಣುಗಳನ್ನು ತಿನ್ನಲು ಕೊಕೊ ಬಾಳೆಹಣ್ಣುಗಳನ್ನು ತಿನ್ನುತ್ತಾನೆ:

ಮೊದಲ ಗಂಟೆ: 23

ಎರಡನೇ ಗಂಟೆ: 7

ಮೂರನೇ ಗಂಟೆ: 11

ನಾಲ್ಕನೇ ಗಂಟೆ: 23

ಐದನೇ ಗಂಟೆ: 4

ಆರನೇ ಗಂಟೆ: 20

ಕೊಕೊ ತಿನ್ನುವ ವಿಧಾನ ಬನಾನಾಸ್ ಲೀಟ್‌ಕೋಡ್ ಪರಿಹಾರ

ಈ ಸಮಸ್ಯೆಯನ್ನು ಪರಿಹರಿಸುವ ಮೊದಲ ಮತ್ತು ಪ್ರಮುಖ ವಿಷಯವೆಂದರೆ ಅವಲೋಕನಗಳನ್ನು ಹೊರತರುವುದು. ನಮ್ಮ ಹುಡುಕಾಟ ಮಧ್ಯಂತರಕ್ಕಾಗಿ ಕೆಲವು ಅವಲೋಕನಗಳು ಇಲ್ಲಿವೆ:

  1. ಕೊಕೊ ಗಂಟೆಗೆ ಕನಿಷ್ಠ ಒಂದು ಬಾಳೆಹಣ್ಣನ್ನು ತಿನ್ನಬೇಕು. ಆದ್ದರಿಂದ ಇದು ಕೆ ಯ ಕನಿಷ್ಠ ಮೌಲ್ಯವಾಗಿದೆ ಪ್ರಾರಂಭಿಸಿ
  2. ಕೊಕೊ ಒಂದು ಗಂಟೆಯಲ್ಲಿ ತಿನ್ನಬಹುದಾದ ಗರಿಷ್ಠ ಸಂಖ್ಯೆಯ ಬಾಳೆಹಣ್ಣುಗಳನ್ನು ನಾವು ರಾಶಿಯಲ್ಲಿ ಗರಿಷ್ಠ ಸಂಖ್ಯೆಯ ಬಾಳೆಹಣ್ಣುಗಳಿಗೆ ಸೀಮಿತಗೊಳಿಸಬಹುದು. ಆದ್ದರಿಂದ ಇದು ಕೆ ಯ ಗರಿಷ್ಠ ಮೌಲ್ಯವಾಗಿದೆ ಅಂತ್ಯ.

ಈಗ ನಾವು ನಮ್ಮ ಹುಡುಕಾಟ ಮಧ್ಯಂತರವನ್ನು ಹೊಂದಿದ್ದೇವೆ. ಮಧ್ಯಂತರದ ಗಾತ್ರ ಎಂದು ಭಾವಿಸೋಣ ಉದ್ದ ಮತ್ತು ರಾಶಿಗಳ ಸಂಖ್ಯೆ n.  ನಿಷ್ಕಪಟ ವಿಧಾನವು ಮಧ್ಯಂತರದಲ್ಲಿನ ಪ್ರತಿಯೊಂದು ಮೌಲ್ಯವನ್ನು ಪರಿಶೀಲಿಸುವುದು. ಕೆ ಕೊಕೊದ ಆ ಮೌಲ್ಯಕ್ಕಾಗಿ ಎಲ್ಲಾ ಬಾಳೆಹಣ್ಣುಗಳನ್ನು ಎಚ್ ಗಂಟೆಯಲ್ಲಿ ಯಶಸ್ವಿಯಾಗಿ ತಿನ್ನಲು ಸಾಧ್ಯವಾದರೆ ಅವುಗಳಲ್ಲಿ ಕನಿಷ್ಠವನ್ನು ಆರಿಸಿ. ನಿಷ್ಕಪಟ ವಿಧಾನದ ಸಮಯದ ಸಂಕೀರ್ಣತೆಯು ಕೆಟ್ಟ ಸಂದರ್ಭದಲ್ಲಿ ಉದ್ದ * n ಆಗಿರುತ್ತದೆ.

ಲೀನಿಯರ್ ಹುಡುಕಾಟದ ಸ್ಥಳದಲ್ಲಿ ಬೈನರಿ ಹುಡುಕಾಟವನ್ನು ಬಳಸುವ ಮೂಲಕ ನಾವು ಸಮಯದ ಸಂಕೀರ್ಣತೆಯನ್ನು ಸುಧಾರಿಸಬಹುದು.

ಬಳಸುವ ಸಮಯದ ಸಂಕೀರ್ಣತೆ ಬೈನರಿ ಹುಡುಕಾಟ ವಿಧಾನವು ಲಾಗ್ ಆಗಿರುತ್ತದೆ (ಉದ್ದ) * 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

ಕೊಕೊ ತಿನ್ನುವ ಬನಾನಾಸ್ ಲೀಟ್‌ಕೋಡ್ ಪರಿಹಾರದ ಸಂಕೀರ್ಣತೆ ವಿಶ್ಲೇಷಣೆ

ಸಮಯದ ಸಂಕೀರ್ಣತೆ

ಮೇಲಿನ ಕೋಡ್‌ನ ಸಮಯದ ಸಂಕೀರ್ಣತೆಯಾಗಿದೆ ಒ (ಎನ್ * ಲಾಗ್ (ಪ)) ಏಕೆಂದರೆ ನಾವು ಒಂದು ಮತ್ತು W ನಡುವೆ ಬೈನರಿ ಹುಡುಕಾಟವನ್ನು ಮಾಡುತ್ತಿದ್ದೇವೆ ಇದು ಲಾಗ್‌ಡಬ್ಲ್ಯೂ ಸಮಯವನ್ನು ತೆಗೆದುಕೊಳ್ಳುತ್ತದೆ ಮತ್ತು ಪ್ರತಿ ಮೌಲ್ಯಕ್ಕೆ, ಬೈನರಿ ಹುಡುಕಾಟದಲ್ಲಿ, ನಾವು ರಾಶಿಗಳ ಶ್ರೇಣಿಯನ್ನು ದಾಟುತ್ತಿದ್ದೇವೆ. ಆದ್ದರಿಂದ ರಾಶಿಗಳು ರಚನೆಯು ಲಾಗ್‌ಡಬ್ಲ್ಯೂ ಬಾರಿ ಹಾದುಹೋಗುತ್ತದೆ, ಇದು ಸಮಯದ ಸಂಕೀರ್ಣತೆಯನ್ನು n * logW ಮಾಡುತ್ತದೆ. ಇಲ್ಲಿ n ಮತ್ತು W ಗಳು ರಾಶಿಗಳ ಸಂಖ್ಯೆ ಮತ್ತು ರಾಶಿಯಲ್ಲಿ ಗರಿಷ್ಠ ಬಾಳೆಹಣ್ಣುಗಳು.

ಬಾಹ್ಯಾಕಾಶ ಸಂಕೀರ್ಣತೆ

ಮೇಲಿನ ಕೋಡ್‌ನ ಸ್ಥಳ ಸಂಕೀರ್ಣತೆಯಾಗಿದೆ ಒ (1) ಏಕೆಂದರೆ ನಾವು ಉತ್ತರವನ್ನು ಸಂಗ್ರಹಿಸಲು ಕೇವಲ ಒಂದು ವೇರಿಯೇಬಲ್ ಅನ್ನು ಬಳಸುತ್ತಿದ್ದೇವೆ.

ಉಲ್ಲೇಖಗಳು