විශාලතම කැන්ඩි ලීට්කෝඩ් විසඳුම සහිත ළමයින්


දුෂ්කරතා මට්ටම පහසු
නිතර අසනු ලැබේ ඇමේසන් බ්ලූම්බර්ග්
අරා

“විශාලතම කැන්ඩි සංඛ්‍යාවක් ඇති ළමයින්” යන ගැටලුවේදී, සමහර ළමයින්ට ලැබී ඇති චොකලට් ගණන සහ ඕනෑම ආකාරයකින් බෙදා හැරිය හැකි අමතර කැන්ඩි වර්ග නියෝජනය කරන පූර්ණ සංඛ්‍යා සමූහයක් අපට ලබා දී ඇත. දැන්, අප සොයා ගත යුත්තේ:

  • සෑම දරුවෙකුටම වැඩිම චොකලට් සංඛ්‍යාවක් තිබිය හැකිද? බෙදා හැරීමෙන් පසු(බහුතරයකින් හෝ ඒකාබද්ධව)?

මෙම හැකියාව අප බූලියන් දෛශික ස්වරූපයෙන් මුද්‍රණය කළ යුතුය.

උදාහරණයක්

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

පැහැදිලි කිරීම

1 වන දරුවා: අපි ඔක්කොම දුන්නත් පළමු දරුවාට අමතර ඉටිපන්දම්, එයට කැන්ඩි 6 ක් ඇත <7 (5 වන දරුවා). ඉතින්, අපි මුද්‍රණය කරනවා බොරු ඒ සඳහා.

2 වන දරුවා: අපි සියල්ල දෙනවා මෙම දරුවාට අමතර ඉටිපන්දම්, එය ගණන් කරයි 9 > 7 (5 වන දරුවා). ඉතින්, අපි මුද්‍රණය කරනවා සැබෑ ඒ සඳහා.

ඒ හා සමානව, තෙවන, සිව්වන සහ පස්වන දරුවා සඳහා ප්‍රශස්ත බෙදාහැරීමෙන් පසු ඔවුන්ට වැඩිම කැන්ඩි ප්‍රමාණයක් තිබිය හැකි බව දැකීම පහසුය.

ප්‍රවේශය (කෑදර)

ගැටලුවේදී, අතිරේක ඉටිපන්දම් බෙදා හැරීම සඳහා අපගේ තේරීමෙන් අපි ස්වාධීන වෙමු. එම ප්රශස්ත ඕනෑම දරුවෙකු සඳහා තීරණය කළ හැකි ක්‍රමය නම් එයට අමතර ඉටිපන්දම් ලබා දී අවශ්‍ය තත්ත්වය පරීක්ෂා කිරීමයි. සලකා බලන්න, අපි ඕනෑම දෙයකට ප්රති result ලය සොයා ගත යුතුය ඉ ළමා. දැන්, එයට ලබා දිය හැකි උපරිම කැන්ඩි ප්‍රමාණය මුළු අමතර කැන්ඩි වලට සමාන වේ.

එබැවින් සන්තකයේ තබා ගත හැකි මුළු ඉටිපන්දම් ගණන ඉ child = a [i] + අමතර ඉටිපන්දම්. මෙම අගය උපරිම මූලද්‍රව්‍යයට වඩා වැඩි නම් අරාව බෙදා හැරීමට පෙර, බෙදා හැරීමෙන් පසු මෙම දරුවාට වැඩිපුරම රසකැවිලි තිබිය හැකි බව අපට නිගමනය කළ හැකිය. අපි සියලු අතිරේක ඉටිපන්දම් ලබා දීමට තෝරා ගන්නා බැවින් ඉ දරුවාට පමණයි, මෙම ප්‍රවේශය කෑදරකම.

විශාලතම කැන්ඩි ලීට්කෝඩ් විසඳුම සහිත ළමයින්

ඇල්ගොරිතම

  1. අරාවෙහි උපරිමය සොයාගෙන එය ලෙස ගබඩා කරන්න maxCandies
  2. බූලියන් ආරම්භ කරන්න ප්රතිඵලය අරාව
  3. අරාව ආරම්භයේ සිට එහි අවසානය දක්වා ලූපයක් ධාවනය කරන්න:
    1. වර්තමාන ඉටිපන්දම් ගණන නම් දරුවා + අමතර ඉටිපන්දම් වේ වඩා විශාල හෝ සමාන වේ maxCandies:
      1. මෙම දරුවාගේ ප්‍රති result ලය ලෙස සකසන්න සැබෑ, බොරු එසේ නොවේ
  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

වැඩිම කැන්ඩි සංඛ්‍යාවක් ඇති ළමයින් සොයා ගැනීමේ සංකීර්ණ විශ්ලේෂණය

කාල සංකීර්ණත්වය

මත), N = අරාවේ ප්‍රමාණය. අපි මුළු අරා එක වරක් ගමන් කරන විට.

අවකාශයේ සංකීර්ණතාව

මත), අපි සෑම දරුවෙකුගේම ප්‍රති result ලය වෙනමම පෙළක් තුළ සුරකිමු.