कँडीज लेटेकोड सोल्यूशनची सर्वात मोठी संख्या असलेले मुले


अडचण पातळी सोपे
वारंवार विचारले ऍमेझॉन ब्लूमबर्ग
अरे

“कँडीजच्या महानतम संख्येसह लहान मुले” या समस्येमध्ये, आम्हाला काही पूर्णांक संख्या दिली गेली आहे जी काही मुलांना मिळालेल्या चॉकलेटची संख्या दर्शविते आणि काही अतिरिक्त कॅंडीज कोणत्याही प्रकारे वितरीत केल्या जाऊ शकतात. आता, आम्हाला शोधण्याची आवश्यकता आहे:

  • प्रत्येक मुलामध्ये चॉकलेटची संख्या मोठी असू शकते? वितरणानंतर(बहुमतासह की संयुक्तपणे)

आम्हाला ही शक्यता बुलियन वेक्टरच्या रूपात मुद्रित करण्याची आवश्यकता आहे.

उदाहरण

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

स्पष्टीकरण

1 ला मूल: जरी आम्ही सर्व दिले पहिल्या मुलाला अतिरिक्त कँडीज, त्यात 6 कॅंडीज <7 (5 वे मूल) असतील. तर आपण प्रिंट करू खोटे त्यासाठी.

2 रा मूल: आम्ही सर्व देतो या मुलाला अतिरिक्त कॅंडीज बनवून, त्याची संख्या बनवते 9 > 7 (5 वे मूल). तर आपण प्रिंट करू खरे त्यासाठी.

त्याचप्रमाणे तिस the्या, चौथ्या आणि पाचव्या मुलासाठी इष्टतम वितरणा नंतर त्यांची संख्या जास्त असू शकते हे पाहणे सोपे आहे.

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

समस्येमध्ये आम्ही अतिरिक्त कँडी वितरित करण्याच्या आमच्या निवडीपासून स्वतंत्र आहोत. द चांगल्या कोणत्याही मुलाचा निर्णय घेण्याचा मार्ग म्हणजे त्यास सर्व अतिरिक्त कँडी द्या आणि मग आवश्यक अट तपासा. विचार करा, आम्हाला कोणत्याहीसाठी निकाल शोधणे आवश्यक आहे आयथ मूल आता त्याला देण्यात येणार्‍या कँडीची जास्तीत जास्त रक्कम एकूण अतिरिक्त कँडीच्या बरोबरीची आहे.

म्हणून, जवळपास कँडीची एकूण संख्या आयथ मूल = अ [i] + अतिरिक्त कँडी. जर हे मूल्य मधील कमाल घटकापेक्षा मोठे असेल अॅरे वितरणापूर्वी, आम्ही असा निष्कर्ष काढू शकतो की या मुलास वितरणानंतर सर्वाधिक कँडी असू शकतात. आम्ही सर्व अतिरिक्त कँडी देणे निवडले असल्याने आयथ फक्त मूल, हा दृष्टीकोन आहे लोभी.

कँडीज लेटेकोड सोल्यूशनची सर्वात मोठी संख्या असलेले मुले

अल्गोरिदम

  1. जास्तीत जास्त अ‍ॅरे शोधा आणि त्यास साठवा मॅक्सकॅंडीज
  2. बुलियन प्रारंभ करा परिणाम अॅरे
  3. अ‍ॅरेच्या सुरूवातीस ते शेवटपर्यंत लूप चालवा:
    1. सध्याच्या कॅंडीजची संख्या असल्यास आयथ मूल + अतिरिक्त कँडी आहे पेक्षा मोठे किंवा समान मॅक्सकॅंडीज:
      1. या मुलाचा निकाल म्हणून सेट करा खरे, खोटे अन्यथा
  4. निकाल प्रिंट करा

कँडीजची सर्वात मोठी संख्या असलेल्या मुलांना शोधण्यासाठी अल्गोरिदमची अंमलबजावणी

सी ++ प्रोग्राम

#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

कँडीजची सर्वात मोठी संख्या असलेल्या मुलांना शोधण्याचे जटिल विश्लेषण

वेळ कॉम्प्लेक्सिटी

ओ (एन), अ‍ॅरेचा एन = आकार. एकदा आपण संपूर्ण अ‍ॅरे ट्रॅव्हर्स केल्यावर.

जागेची जटिलता

ओ (एन), जसे की आम्ही प्रत्येक मुलाचा निकाल वेगळ्या अ‍ॅरेमध्ये सेव्ह करतो.