कैंडीज लेटेकोड सॉल्यूशन की सबसे बड़ी संख्या के साथ बच्चे


कठिनाई स्तर आसान
में अक्सर पूछा वीरांगना ब्लूमबर्ग
ऐरे

"बच्चों के साथ सबसे बड़ी संख्या में कैंडीज" की समस्या में, हमें एक पूर्णांक दिया जाता है जो कुछ बच्चों को मिली चॉकलेट की संख्या का प्रतिनिधित्व करता है और कुछ अतिरिक्त कैंडीज जिन्हें किसी भी तरीके से वितरित किया जा सकता है। अब, हमें खोजने की आवश्यकता है:

  • क्या हर बच्चे के पास सबसे बड़ी संख्या में चॉकलेट हो सकते हैं वितरण के बाद(या तो बहुमत से या संयुक्त रूप से)?

हमें बूलियन वेक्टर के रूप में इस संभावना को प्रिंट करने की आवश्यकता है।

उदाहरण

Array = {1 , 4 , 5 , 6 , 7}
Extra = 5
false true true true true

व्याख्या

पहला बच्चा: भले ही हमने सब दिया पहले बच्चे को अतिरिक्त कैंडी, इसमें 6 कैंडी <7 (5 वां बच्चा) होगा। तो, हम प्रिंट करते हैं असत्य इसके लिए।

दूसरा बच्चा: हम सब देते हैं इस बच्चे को अतिरिक्त कैंडी, इसकी गिनती बना रही है 9 > 7 (5 वां बच्चा)। तो, हम प्रिंट करते हैं <strong>उद्देश्य</strong> इसके लिए।

इसी तरह, तीसरे, चौथे और पांचवें बच्चे के लिए यह देखना आसान है कि इष्टतम वितरण के बाद उनके पास सबसे बड़ी संख्या में कैंडीज हो सकते हैं।

दृष्टिकोण (लालची)

समस्या में, हम अतिरिक्त कैंडी वितरित करने के लिए अपनी पसंद से स्वतंत्र हैं। इष्टतम किसी भी बच्चे के लिए निर्णय लेने का तरीका यह होगा कि वह सभी अतिरिक्त कैंडी दे और फिर आवश्यक स्थिति की जांच करें। विचार करें, हमें किसी भी परिणाम का पता लगाने की आवश्यकता है ith बच्चा। अब, दी जाने वाली कैंडी की अधिकतम मात्रा कुल अतिरिक्त कैंडी के बराबर है।

इसलिए, कैंडी की कुल संख्या, जिसके पास हो सकती है ith बच्चा = एक [i] + अतिरिक्त कैंडी। यदि यह मान अधिकतम तत्व से अधिक है सरणी वितरण से पहले, हम यह निष्कर्ष निकाल सकते हैं कि वितरण के बाद इस बच्चे के पास सबसे अधिक कैंडी हो सकती है। चूंकि हम सभी अतिरिक्त कैंडी को देने के लिए चुनते हैं ith बच्चा ही, यह दृष्टिकोण है लालची.

कैंडीज लेटेकोड सॉल्यूशन की सबसे बड़ी संख्या के साथ बच्चे

कलन विधि

  1. सरणी का अधिकतम पता लगाएं और इसे स्टोर करें अधिकतम
  2. एक बूलियन को प्रारंभ करें परिणाम सरणी
  3. सरणी के आरंभ से अंत तक एक लूप चलाएं:
    1. यदि कैंडी की वर्तमान संख्या ith बच्चा + अतिरिक्त कैंडी है इससे बड़ा या इसके बराबर अधिकतम
      1. इस बच्चे के परिणाम के रूप में सेट करें <strong>उद्देश्य</strong>, असत्य अन्यथा
  4. परिणाम प्रिंट करें

कैंडीज की सबसे बड़ी संख्या के साथ बच्चों को खोजने के लिए एल्गोरिथ्म का कार्यान्वयन

C ++ प्रोग्राम

#include <bits/stdc++.h>
using namespace std;

vector <bool> kidsWithCandies(vector <int> &candies , int extraCandies)
{
    int n = candies.size() , maxCandies = 0;
    for(int i = 0 ; i < n ; i++)
        if(candies[i] > maxCandies)
            maxCandies = candies[i];


    vector <bool> result(n);
    for(int i = 0 ; i < n ; i++)
        result[i] = (candies[i] + extraCandies >= maxCandies);

    return result;
}


int main()
{
    vector <int> candies = {1 , 4 , 5 , 6 , 7};
    int extraCandies = 5;
    for(bool x : kidsWithCandies(candies , extraCandies))
        cout << (x ? "true" : "false") << " ";
    cout << '\n';
    return 0;
}

जावा प्रोग्राम

class kids_with_candies
{
    public static void main(String args[])
    {
        int[] candies = {1 , 4 , 5 , 6 , 7};
        int extraCandies = 5;
        for(boolean x : kidsWithCandies(candies , extraCandies))
            System.out.print(x + " ");
    }


    static boolean[] kidsWithCandies(int[] candies , int extraCandies)
    {
        int n = candies.length , maxCandies = 0;
        for(int i = 0 ; i < n ; i++)
            if(candies[i] > maxCandies)
                maxCandies = candies[i];

        boolean[] result = new boolean[n];

        for(int i = 0 ; i < n ; i++)
            result[i] = (candies[i] + extraCandies >= maxCandies);

        return result;
    }
}
false true true true true

बच्चों की सबसे बड़ी संख्या कैंडी के साथ खोजने की जटिलता विश्लेषण

समय जटिलता

पर), सरणी का एन = आकार। जैसा कि हम एक बार पूरे सरणी को पार करते हैं।

अंतरिक्ष की जटिलता

पर), जैसा कि हम हर बच्चे के परिणाम को एक अलग सरणी में सहेजते हैं।