ഏറ്റവും വലിയ എണ്ണം കാൻഡീസ് ലീറ്റ്കോഡ് പരിഹാരമുള്ള കുട്ടികൾ


വൈഷമ്യ നില എളുപ്പമായ
പതിവായി ചോദിക്കുന്നു ആമസോൺ ബ്ലൂംബർഗ്
അറേ

“ഏറ്റവും വലിയ എണ്ണം മിഠായികളുള്ള കുട്ടികൾ” എന്ന പ്രശ്‌നത്തിൽ, ചില കുട്ടികൾക്ക് ലഭിച്ച ചോക്ലേറ്റുകളുടെ എണ്ണത്തെയും ഏതെങ്കിലും വിധത്തിൽ വിതരണം ചെയ്യാൻ കഴിയുന്ന ചില അധിക മിഠായികളെയും പ്രതിനിധീകരിക്കുന്ന സംഖ്യകളുടെ ഒരു നിര ഞങ്ങൾക്ക് നൽകിയിരിക്കുന്നു. ഇപ്പോൾ, ഞങ്ങൾ കണ്ടെത്തേണ്ടതുണ്ട്:

  • ഓരോ കുട്ടിക്കും ഏറ്റവും കൂടുതൽ ചോക്ലേറ്റുകൾ ഉണ്ടോ? വിതരണത്തിന് ശേഷം(ഒന്നുകിൽ ഭൂരിപക്ഷത്തോടെയോ അല്ലെങ്കിൽ സംയുക്തമായി)?

ഈ സാധ്യത ഒരു ബൂളിയൻ വെക്റ്ററിന്റെ രൂപത്തിൽ ഞങ്ങൾ പ്രിന്റുചെയ്യേണ്ടതുണ്ട്.

ഉദാഹരണം

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

വിശദീകരണം

ആദ്യ കുട്ടി: ഞങ്ങൾ എല്ലാം നൽകിയാലും ആദ്യ കുട്ടിക്ക് അധിക മിഠായികൾ, അതിൽ 6 മിഠായികൾ <7 (അഞ്ചാമത്തെ കുട്ടി) ഉണ്ടാകും. അതിനാൽ, ഞങ്ങൾ അച്ചടിക്കുന്നു തെറ്റായ ഇതിനുവേണ്ടി.

രണ്ടാമത്തെ കുട്ടി: ഞങ്ങൾ എല്ലാം നൽകുന്നു ഈ കുട്ടിക്ക് അധിക മിഠായികൾ, അതിന്റെ എണ്ണം കണക്കാക്കുന്നു 9 > 7 (അഞ്ചാമത്തെ കുട്ടി). അതിനാൽ, ഞങ്ങൾ അച്ചടിക്കുന്നു യഥാർഥ ഇതിനുവേണ്ടി.

അതുപോലെ, മൂന്നാമത്തെയും നാലാമത്തെയും അഞ്ചാമത്തെയും കുട്ടിക്ക്, ഒപ്റ്റിമൽ വിതരണത്തിനുശേഷം അവർക്ക് ഏറ്റവും കൂടുതൽ മിഠായികൾ ഉണ്ടെന്ന് കാണാൻ എളുപ്പമാണ്.

സമീപനം (അത്യാഗ്രഹം)

പ്രശ്‌നത്തിൽ, അധിക മിഠായികൾ വിതരണം ചെയ്യുന്നതിനുള്ള ഞങ്ങളുടെ തിരഞ്ഞെടുപ്പിൽ നിന്ന് ഞങ്ങൾ സ്വതന്ത്രരാണ്. ദി ഒപ്റ്റിമൽ ഏതൊരു കുട്ടിക്കും തീരുമാനിക്കാനുള്ള മാർഗം അതിന് എല്ലാ അധിക മിഠായികളും നൽകി ആവശ്യമായ അവസ്ഥ പരിശോധിക്കുക എന്നതാണ്. പരിഗണിക്കുക, ഏതൊരാൾ‌ക്കും ഞങ്ങൾ‌ ഫലം കണ്ടെത്തേണ്ടതുണ്ട് ith കുട്ടി. ഇപ്പോൾ, അതിന് നൽകാൻ കഴിയുന്ന പരമാവധി മിഠായികൾ മൊത്തം അധിക മിഠായികൾക്ക് തുല്യമാണ്.

അതിനാൽ, കൈവശം വയ്ക്കാവുന്ന മിഠായികളുടെ ആകെ എണ്ണം ith കുട്ടി = a [i] + അധിക മിഠായികൾ. ഈ മൂല്യം ലെ പരമാവധി ഘടകത്തേക്കാൾ വലുതാണെങ്കിൽ ശ്രേണി വിതരണത്തിന് മുമ്പ്, വിതരണത്തിന് ശേഷം ഏറ്റവും കൂടുതൽ മിഠായികൾ ഈ കുട്ടിക്ക് ഉണ്ടെന്ന് ഞങ്ങൾക്ക് നിഗമനം ചെയ്യാം. എല്ലാ അധിക മിഠായികളും നൽകാൻ ഞങ്ങൾ തിരഞ്ഞെടുക്കുന്നതിനാൽ ith കുട്ടി മാത്രം, ഈ സമീപനം അത്യാഗ്രഹം.

ഏറ്റവും വലിയ എണ്ണം കാൻഡീസ് ലീറ്റ്കോഡ് പരിഹാരമുള്ള കുട്ടികൾ

അൽഗോരിതം

  1. അറേയുടെ പരമാവധി കണ്ടെത്തി ഇതായി സംഭരിക്കുക maxCandies
  2. ഒരു ബൂളിയൻ സമാരംഭിക്കുക ഫലം ശ്രേണി
  3. അറേയുടെ ആരംഭം മുതൽ അവസാനം വരെ ഒരു ലൂപ്പ് പ്രവർത്തിപ്പിക്കുക:
    1. ന്റെ മിഠായികളുടെ എണ്ണം എങ്കിൽ ith കുട്ടി + അധിക മിഠായികൾ വലുതോ തുല്യമോ maxCandies:
      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

ഏറ്റവും വലിയ എണ്ണം മിഠായികളുള്ള കുട്ടികളെ കണ്ടെത്തുന്നതിനുള്ള സങ്കീർണ്ണത വിശകലനം

സമയ സങ്കീർണ്ണത

O (N), N = അറേയുടെ വലുപ്പം. ഞങ്ങൾ മുഴുവൻ അറേയും ഒരു തവണ സഞ്ചരിക്കുമ്പോൾ.

സ്ഥല സങ്കീർണ്ണത

O (N), ഓരോ കുട്ടിയുടെയും ഫലം ഞങ്ങൾ ഒരു പ്രത്യേക അറേയിൽ സംരക്ഷിക്കുമ്പോൾ.