বাচ্চাদের সাথে গ্রেড সংখ্যক ক্যান্ডিজ লেটকোড সলিউশন


কাঠিন্য মাত্রা সহজ
প্রায়শই জিজ্ঞাসা করা হয় মর্দানী স্ত্রীলোক ব্লুমবার্গ
বিন্যাস

"গ্রেড সর্বাধিক সংখ্যক ক্যান্ডির সংখ্যায় বাচ্চাদের" সমস্যাটিতে, আমাদের কিছুসংখ্যক পূর্ণসংখ্যার অ্যারে দেওয়া হয় যা কিছু শিশুদের চকোলেটের সংখ্যার প্রতিনিধিত্ব করে এবং কিছু অতিরিক্ত ক্যান্ডিগুলি যে কোনও উপায়ে বিতরণ করা যায়। এখন, আমাদের সন্ধান করা দরকার:

  • প্রতিটি সন্তানের কি চকোলেটের সর্বাধিক সংখ্যা থাকতে পারে? বিতরণ পরে(হয় সংখ্যাগরিষ্ঠের সাথে বা যৌথভাবে)?

আমাদের এই সম্ভাবনাটি বুলিয়ান ভেক্টর আকারে মুদ্রণ করা দরকার।

উদাহরণ

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

ব্যাখ্যা

1 ম শিশু: যদিও আমরা সব দিয়েছি প্রথম সন্তানের অতিরিক্ত ক্যান্ডিসের সাথে এতে 6 টি ক্যান্ডি থাকবে <7 (5 ম সন্তান)। সুতরাং, আমরা মুদ্রণ মিথ্যা এর জন্য.

২ য় সন্তান: আমরা সব দিই এই শিশুর অতিরিক্ত ক্যান্ডিগুলি তৈরি করে, এটির সংখ্যা গুনে 9 > 7 (5 ম শিশু)। সুতরাং, আমরা মুদ্রণ সত্য এর জন্য.

একইভাবে, তৃতীয়, চতুর্থ এবং পঞ্চম সন্তানের পক্ষে এটি সহজেই দেখতে পাওয়া যায় যে সর্বোত্তম বিতরণের পরে তাদের সর্বাধিক সংখ্যক ক্যান্ডি থাকতে পারে।

পদ্ধতির (লোভী)

সমস্যাটিতে অতিরিক্ত ক্যান্ডি বিতরণ করার জন্য আমরা আমাদের পছন্দ থেকে স্বাধীন। দ্য অনুকূল যে কোনও সন্তানের সিদ্ধান্ত নেওয়ার উপায়টি হ'ল এটি সমস্ত অতিরিক্ত ক্যান্ডি দেওয়া এবং তারপরে প্রয়োজনীয় শর্তটি পরীক্ষা করা। বিবেচনা করুন, আমাদের যে কোনওটির জন্য ফলাফল বের করা দরকার সন্তান শিশু এখন, সর্বাধিক পরিমাণ ক্যান্ডিগুলি এটি দেওয়া যায় এটি মোট অতিরিক্ত ক্যান্ডির সমান।

অতএব, মোট ক্যান্ডিসের সংখ্যাটি যেগুলি ধারণ করতে পারে সন্তান শিশু = ক [i] + অতিরিক্ত ক্যান্ডিস ies যদি এই মানটি সর্বাধিক উপাদানের চেয়ে বেশি হয় বিন্যাস বিতরণের আগে, আমরা এই সিদ্ধান্ত নিতে পারি যে বিতরণের পরে এই সন্তানের সবচেয়ে বেশি ক্যান্ডি থাকতে পারে। যেহেতু আমরা সমস্ত অতিরিক্ত ক্যান্ডি দেওয়া পছন্দ করি সন্তান সন্তানের শুধুমাত্র, এই পদ্ধতির হয় লোভী.

বাচ্চাদের সাথে গ্রেড সংখ্যক ক্যান্ডিজ লেটকোড সলিউশন

অ্যালগরিদম

  1. অ্যারের সর্বাধিক সন্ধান করুন এবং এটি হিসাবে সংরক্ষণ করুন maxCandies
  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

ক্যান্ডিসের সর্বাধিক সংখ্যক বাচ্চাদের সন্ধানের জটিলতা বিশ্লেষণ

সময় জটিলতা

চালু), অ্যারের N = আকার। আমরা একবারে পুরো অ্যারেটি অতিক্রম করি।

স্থান জটিলতা

চালু), যেহেতু আমরা প্রতিটি সন্তানের ফলাফলকে আলাদা অ্যারেতে সংরক্ষণ করি।