के विद्यार्थ्यांमधे समान प्रमाणात वितरित केले जास्तीत जास्त चॉकलेटची संख्या


अडचण पातळी मध्यम
वारंवार विचारले ऐक्सचर अडोब ऍमेझॉन फेसबुक फोरकाइट्स
अरे हॅश

“के विद्यार्थ्यांमध्ये समान प्रमाणात वितरित होणारी जास्तीत जास्त चॉकलेट्स” असे नमूद करते की आपणास एन बॉक्स देण्यात आले आहेत ज्यात काही चॉकलेट्स आहेत. समजा तेथे के विद्यार्थी आहेत. सलग बॉक्स निवडून के विद्यार्थ्यांमध्ये तितकीच चॉकलेट समान प्रमाणात वितरित करण्याचे कार्य आहे. आम्ही असे समजू शकतो की बॉक्स एका ओळीत आहेत ज्यात 1 ते n पर्यंतच्या संख्ये आहेत. कार्य म्हणजे बॉक्सच्या गटाची निवड करणे जे के. विद्यार्थ्यांना जास्त प्रमाणात चॉकलेट वितरित करू शकेल. दिलेली पेटी अ‍ॅरे मानली जाऊ शकतात आणि अ‍ॅर [i] प्रथम निर्देशांकच्या स्थानावर त्यामधील चॉकलेटची संख्या दर्शवू शकतात.

उदाहरण

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

k = 3
8

स्पष्टीकरण: सब एरे 5, 3, 6, 10 मधील संख्या 24 चॉकलेट्स आहेत ज्या के विद्यार्थ्यांमध्ये वितरित केल्या जाऊ शकतात. म्हणजे प्रति विद्यार्थी 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. सारखा टेम्प आहे. तर आपण पुढे जाऊ. इतर स्थितीत. परंतु आमच्याकडे आधीपासूनच नकाशामध्ये आहे. आपण नकाशात 1 आणि 0 संग्रहित केल्यामुळे आपल्याला त्याचे मूल्य मिळेल आणि ते 1 आहे. मग आपण [i] -सूम [0] ची बेरीज शोधू आणि ती 0 होईल, परिणामी या क्रमांकावर अद्यतनित होईल.

अजून एका नंबरला भेट दिल्यानंतर आमच्याकडे उत्तर 24 इतकेच आहे. शेवटी, आम्ही 24/3 परत करू म्हणजे 8. हे आपले अंतिम उत्तर असेल.

के विद्यार्थ्यांमधे समान प्रमाणात वितरित केले जास्तीत जास्त चॉकलेटची संख्या

अंमलबजावणी

के + विद्यार्थ्यांमध्ये समान प्रमाणात वितरित होणार्‍या जास्तीत जास्त चॉकलेटसाठी सी ++ प्रोग्राम

#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

के विद्यार्थ्यांमधील जास्तीत जास्त चॉकलेट वितरित करण्यासाठी कॉम्प्लेक्सिटी विश्लेषण

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

O (n) जेथे “एन” अ‍ॅरे मधील घटकांची संख्या.

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

O (n) जेथे “एन” अ‍ॅरे मधील घटकांची संख्या.

संदर्भ