ছাত্রছাত্রীদের মধ্যে সমানভাবে বিতরণের জন্য চকোলেটগুলির সর্বাধিক সংখ্যা


কাঠিন্য মাত্রা মধ্যম
প্রায়শই জিজ্ঞাসা করা হয় Accenture রৌদ্রপক্ব ইষ্টক মর্দানী স্ত্রীলোক ফেসবুক ফোরকিটস
বিন্যাস কাটা

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

উদাহরণ

arr[] = {1, 5, 3, 6, 10, 1}

k = 3
8

ব্যাখ্যা: উপ-অ্যারে 5, 3, 6, 10 এর সংখ্যা 24 টি চকোলেট যা কে শিক্ষার্থীদের মাঝে বিতরণ করা যায় constitu তার মানে প্রতি শিক্ষার্থী 8 টি চকোলেট যা প্রদত্ত মানের সর্বাধিক।

অ্যালগরিদম

1. Declare a map.
2. Declare an array ‘sum’ of size n (length of the given array).
3. Set resultant to 0 and copy the value of arr[0] to sum[0].
4. Add all the values of arr[i] and sum[i-1] and store each value at sum[i].
5. Traverse the array, while i < n (length of the array).
  1. Set temp to sum[i]%k and check if the temp is equal to 0.
    1. If true then check for if resultant is less than sum[i], if true, then update resultant = sum[i].
  2. Check if the temp is present in a map, if present, then, push this value and the current index into the map.
  3. Else get the number which is related with the temp in a map, let x= map[temp], check if resultant is less than the sum[i] –sum[x].
    1. If true then update the value of resultant=sum[i]-sum[x], where x is map[temp].
6. Return the (resultant / k ).

ব্যাখ্যা

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

আমরা ব্যবহার করতে যাচ্ছি হ্যাশ। আমরা একটি ঘোষণা করব মানচিত্র। তবে, এর আগে আমরা একটি খালি অ্যারে তৈরি করব, প্রদত্ত অ্যারে হিসাবে একই আকারের, যে এন। [0] আরার হিসাবে মান যোগফল [0] নির্ধারণ করুন, এর অর্থ যোগারের প্রথম মান [0] আরারের মতো হওয়া উচিত [0]। ট্র্যাভার করার সময় বিন্যাস, আমরা অ্যারে যুক্ত করব [i] এবং যোগফল [i-1] এবং সমষ্টিতে মান সংরক্ষণ করব [i], এই পদ্ধতিতে আমরা একটি অ্যারের এবং যোগফলের পূর্ববর্তী সূচক উপাদানগুলির মান যুক্ত করব। আমাদের এটির যোগফলের মান হবে।

আসুন আমরা এর উদাহরণ নিই:

উদাহরণ

আরআর [] = {1, 5, 3, 6, 10, 1}, কে = 3

যোগফল [0] = আরআর [0] = 1।

যোগফল [1] = আরআর [i] + যোগ [i-1] = 6,

যোগফল [2] = অ্যারে [i] + যোগ [i-1] = 9, এটি অবিরত রাখলে আমাদের যোগফলের অ্যারেতে নিম্নোক্ত মান থাকবে।

যোগফল [] = {1, 6, 9, 15, 25, 26}।

আমরা আবার অ্যারেটি অতিক্রম করব, সাময়িকভাবে [i]% কে যোগ করব। টেম্পারটি 0 এর সমান হয় কিনা তা আমরা খতিয়ে দেখব, তবে তা নয়, তাই আমরা মানচিত্রটিতে এই মানটি নেই কিনা তা খতিয়ে দেখব, আমরা এটি বর্তমান মানচিত্রের সাথে একটি মানচিত্রে রেখে দেব। সুতরাং মানচিত্রে, আমাদের এখন (1,0) আছে।

পরবর্তী 6 নম্বর বাছাই করা এবং অস্থায়ী হিসাবে [i]% কে যোগফল পরীক্ষা করা এখন 0 হিসাবে পাওয়া গেছে, সুতরাং আমরা এখন ফলাফলটি আপডেট করব। ফলাফল 6 হবে।

পরবর্তী উপাদানটি 9 এবং 15 হবে, এই প্যাটার্নে উভয়টির মডিউল 3 থেকে 0 হয়, সুতরাং 15 পর্যন্ত, ফলাফলটি 15 হবে। পরের সংখ্যাটি 25, আমাদের এখন 1 এর মতো টেম্পোর রয়েছে So অন্য অবস্থায়। তবে মানচিত্রে ইতিমধ্যে আমাদের 1 টি রয়েছে। সুতরাং আমরা এর মান পাব এবং এটি 0, যেমন আমরা মানচিত্রে 1 এবং 0 সংরক্ষণ করেছি। তারপরে আমরা যোগফলটি [i] -সুম [0] খুঁজে বের করব এবং এটি 24 হবে, এই সংখ্যার আপডেট ফলাফল।

আরও একটি নম্বর দেখার পরে, 24 এর মতো আমাদের কাছে এখনও উত্তর রয়েছে Finally অবশেষে, আমরা 24/3 যা 8 হ'ল XNUMX এটি আমাদের চূড়ান্ত উত্তর হবে।

ছাত্রছাত্রীদের মধ্যে সমানভাবে বিতরণের জন্য চকোলেটগুলির সর্বাধিক সংখ্যা

বাস্তবায়ন

কে + শিক্ষার্থীদের মধ্যে সমানভাবে বিতরণ করা সর্বাধিক সংখ্যক চকোলেটের জন্য সি ++ প্রোগ্রাম

#include<iostream>
#include<unordered_map>

using namespace std;

int getChocolateNumbers(int arr[], int n, int k)
{
    unordered_map<int, int> MAP;

    int sum[n];

    int resultant = 0;

    sum[0] = arr[0];
    for (int i = 1; i < n; i++)
        sum[i] = sum[i - 1] + arr[i];

    for (int i = 0; i < n; i++)
    {
        int temp = sum[i] % k;

        if (temp == 0)
        {
            if (resultant < sum[i])
                resultant = sum[i];
        }
        else if (MAP.find(temp) == MAP.end())
            MAP[temp] = i;

        else if (resultant < (sum[i] - sum[MAP[temp]]))
            resultant = sum[i] - sum[MAP[temp]];
    }
    return (resultant / k);
}
int main()
{
    int arr[] = {1, 5, 3, 6, 10, 1};
    int n = sizeof(arr) / sizeof(arr[0]);
    int k = 3;
    cout << "Number of chocolates which can be equally distributed:  "<< getChocolateNumbers(arr, n, k);
    return 0;
}
Number of chocolates which can be equally distributed:  8

সর্বাধিক সংখ্যক চকোলেটের জন্য জাভা প্রোগ্রাম কে শিক্ষার্থীদের মাঝে সমানভাবে বিতরণ করা

import java.util.HashMap;

class distributionOfChocolates
{
    public static int getChocolateNumbers(int arr[], int n, int k)
    {
        HashMap <Integer,Integer> MAP = new HashMap<Integer,Integer>();

        int sum[]=new int[n];

        int resultant = 0;

        sum[0] = arr[0];
        for (int i = 1; i < n; i++)
        {
            sum[i] = sum[i - 1] + arr[i];
        }
        for (int i = 0; i < n; i++)
        {
            int temp = sum[i] % k;

            if (temp == 0)
            {
                if (resultant < sum[i])
                    resultant = sum[i];
            }

            else if (!MAP.containsKey(temp) )
                MAP.put(temp, i);

            else if (resultant < (sum[i] - sum[MAP.get(temp)]))
                resultant = sum[i] - sum[MAP.get(temp)];
        }

        return (resultant / k);
    }
    public static void main(String[] args)
    {
        int arr[] = { 1,5,3,6,10,1 };
        int n = arr.length;
        int k = 3;
        System.out.println("Number of chocolates which can be equally distributed: "+ getChocolateNumbers(arr, n, k));
    }
}
Number of chocolates which can be equally distributed: 8

শিক্ষার্থীদের মধ্যে সমানভাবে বিতরণের জন্য চকোলেটগুলির সর্বাধিক সংখ্যার জন্য জটিলতা বিশ্লেষণ

সময় জটিলতা

উপর) কোথায় "এন" অ্যারেতে উপাদানগুলির সংখ্যা।

স্পেস জটিলতা ity

উপর) কোথায় "এন" অ্যারেতে উপাদানগুলির সংখ্যা।

উল্লেখ