बच्चाहरू क्यान्डीज लेटेकोड समाधानको सबैभन्दा ठूलो संख्याको साथ


कठिनाई तह सजिलो
बारम्बार सोधिन्छ अमेजन ब्लूमबर्ग
एरे

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

  • के प्रत्येक बच्चासँग चकलेटको ठूलो संख्या हुन सक्छ? वितरण पछि(या त बहुमतको साथ वा संयुक्त रूपमा)?

हामीले यो सम्भावना बुलियन भेक्टरको रूपमा प्रिन्ट गर्न आवश्यक पर्दछ।

उदाहरणका

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

स्पष्टीकरण

पहिलो बच्चा: हामी सबै दिए पनि पहिलो बच्चालाई अतिरिक्त क्यान्डीहरू, यसमा cand क्यान्डीहरू <((6th औं बच्चा) हुनेछ। त्यसो भए, हामी प्रिन्ट गर्छौं झूटा यसको लागी।

दोस्रो बच्चा: हामी सबै दिन्छौं यस बच्चालाई थप क्यान्डीहरू बनाउँदछ, यसलाई काउन्ट बनाउँदै 9 > ((7th औं बच्चा) त्यसो भए, हामी प्रिन्ट गर्छौं साँचो यसको लागी।

त्यस्तै, तेस्रो, चौथो र पाँचौं बच्चाको लागि यो देख्न सजिलो छ कि उनीहरू अधिकतम वितरण पछि क्यान्डीहरूको स number्ख्यामा धेरै हुन सक्छन्।

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

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

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

बच्चाहरू क्यान्डीज लेटेकोड समाधानको सबैभन्दा ठूलो संख्याको साथ

अल्गोरिदम

  1. एर्रेको अधिकतम फेला पार्नुहोस् र यसलाई भण्डार गर्नुहोस् maxCandies
  2. बुलियन सुरु गर्नुहोस् परिणाम array
  3. एर्रेको सुरूवातबाट अन्त्यसम्म लूप चलाउनुहोस्:
    1. यदि हालको क्यान्डीहरूको संख्या ith बच्चा + अतिरिक्त क्यान्डी हो भन्दा ठूलो वा बराबर अधिकतम क्यांडीज:
      1. को रूपमा यस बच्चाको नतिजा सेट गर्नुहोस् साँचो, झूटा अन्यथा
  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

क्यान्डीहरूको सबैभन्दा ठूलो संख्याको साथ बच्चाहरू फेला पार्ने जटिलता विश्लेषण

समय जटिलता

O (N), N = एर्रेको आकार। जब हामी सम्पूर्ण एर्रे एक पटक ट्रान्सवार्स गर्छौं।

ठाउँ जटिलता

O (N), हामी प्रत्येक बच्चाको नतिजा अलग एर्रेमा सुरक्षित गर्छौं।