מאַקסימום נומער פון טשאָקלאַץ צו זיין פונאנדערגעטיילט גלייַך צווישן ק סטודענטן  


שוועריקייט לעוועל מיטל
אָפט געבעטן אין אַקסענטורע אַדאָובי אַמאַזאָן facebook פאָורקיטעס
מענגע האַש

"די מאַקסימום נומער פון טשאָקלאַץ צו זיין פונאנדערגעטיילט גלייַך צווישן ק סטודענטן" זאגט אַז איר האָט N באָקסעס מיט עטלעכע טשאָקלאַץ. רעכן עס זענען ק סטודענטן. די אַרבעט איז צו פאַרשפּרייטן די מאַקסימום נומער פון טשאָקלאַץ גלייַך דורך ק סטודענטן דורך סעלעקטינג קאָנסעקוטיווע באָקסעס. מיר קענען יבערנעמען אַז באָקסעס זענען אין אַ רודערן פון נומערן 1 צו n. די אַרבעט איז צו סעלעקטירן אַ גרופּע פון ​​באָקסעס וואָס קענען פאַרשפּרייטן די מערסט נומער פון טשאָקלאַץ צו די סטודענטן גלייַך. די באָקסעס וואָס זענען געגעבן קענען ווערן באטראכט ווי אַ מענגע און אַרר [איך] קענען רעפּראַזענץ די נומער פון טשאָקלאַץ אין עס אויף דער שטעלע פון ​​י'ט אינדעקס.

בייַשפּיל  

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 ).

דערקלערונג  

מיר האָבן געגעבן די אַרבעט צו פאַרשפּרייטן די מאַקסימום טשאָקלאַץ גלייַך צווישן ק סטודענטן. די קעסטל איז בייסיקלי אַ מענגע וואָס רעפּראַזענץ די נומער פון טשאָקלאַץ. איין צושטאַנד איז אויך דאָרט, מיר מוזן קלייַבן קאָנסעקוטיווע באָקסעס צו פאַרשפּרייטן טשאָקלאַץ און די פאַרשפּרייטונג זאָל זיין מאַקסאַמייזד.

זע אויך
דאַטן סטרוקטור דיזיינינג

מיר וועלן נוצן כאַשינג. מיר וועלן דערקלערן א מאַפּע. איידער, מיר וועלן מאַכן אַ ליידיק מענגע, פון דער זעלביקער גרייס ווי די געגעבן מענגע, וואָס איז N. באַשטעטיק די ווערט סומע [0] ווי פון אַרר [0], מיטל דער ערשטער ווערט פון סאַכאַקל [0] זאָל זיין די זעלבע ווי אַרר [0]. בשעת טראַווערסינג די מענגע, מיר וועלן לייגן די אַרר [i] און סומע [i-1] און קראָם די ווערט אין סומע [i]. אויף דעם שטייגער, מיר וועלן לייגן אַרויף די וואַלועס פון אַ מענגע און די סומע פון ​​די פריערדיקע ינדעקסיז עלעמענט. מיר וועלן האָבן די סומע פון ​​די וואַלועס.

לאָמיר נעמען אַ בייַשפּיל פון אים:

בייַשפּיל

אַרר [] = {1, 5, 3, 6, 10, 1}, ק = 3

סומע [0] = אַרר [0] = 1.

סאַכאַקל [1] = אַרר [איך] + סומע [איך -1] = 6,

סאַכאַקל [2] = אַרר [איך] + סאַכאַקל [איך -1] = 9, פאָרזעצן עס, מיר וועלן האָבן די פאלגענדע וואַלועס אין סומע מענגע.

סומע [] = {1, 6, 9, 15, 25, 26}.

מיר וועלן אַריבער די מענגע ווידער, פּיקינג אַרויף טעמפּ ווי סומע [i]% ק. מיר וועלן קאָנטראָלירן אויב די טעמפּ איז גלייַך צו 0, אָבער עס איז נישט, אַזוי מיר וועלן טשעק אויב די מאַפּע כּולל נישט דעם ווערט, מיר וועלן שטעלן עס מיט די קראַנט אינדעקס אין אַ מאַפּע. אַזוי אויף דער מאַפּע, מיר האָבן איצט (1,0).

פּיקינג אַרויף די ווייַטער נומער 6 און קאָנטראָלירן סומע [i]% k ווי אַ טעמפּ, איז געפֿונען צו זיין איצט 0, אַזוי מיר וועלן דערהייַנטיקן די ריזאַלטאַנט איצט. דער רעזולטאַט וואָלט זיין 6.

דער ווייַטער עלעמענט וואָלט זיין 9 און 15, אין דעם מוסטער ביידע האָבן מאָדולאָ צו 3 איז 0, אַזוי אַרויף צו 15, די ריזאַלטאַנט וואָלט זיין 15. דער ווייַטער נומער איז 25, מיר האָבן אַ טעמפּ איצט ווי 1. אַזוי מיר וועלן שפּרינגען אויף צו די אַנדערש צושטאַנד. אָבער מיר האָבן שוין 1 אין דער מאַפּע. אַזוי מיר וועלן באַקומען די ווערט פון עס און דאָס איז 0, ווייַל מיר סטאָרד 1 און 0 אין דער מאַפּע. דערנאָך מיר וועלן געפֿינען די סומע [i] -sum [0], און דאָס וועט זיין 24, דערהייַנטיקן ריזאַלטאַנט צו דעם נומער.

זע אויך
געפֿינען אַ סאָרטעד סאַבסאַקוואַנס פון גרייס 3 אין לינעאַר צייט

נאָך באזוכן איין נומער, מיר נאָך האָבן די ענטפער ווי עס איז 24. לעסאָף, מיר וועלן צוריקקומען 24/3 אַז איז 8. דאָס וועט זיין אונדזער לעצט ענטפער.

מאַקסימום נומער פון טשאָקלאַץ צו זיין פונאנדערגעטיילט גלייַך צווישן ק סטודענטןשפּילקע

ימפּלעמענטאַטיאָן  

C ++ פּראָגראַם פֿאַר מאַקסימום נומער פון טשאָקלאַץ צו זיין פונאנדערגעטיילט גלייַך צווישן ק סטודענטן

#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

Java פּראָגראַם פֿאַר מאַקסימום נומער פון טשאָקלאַץ צו זיין פונאנדערגעטיילט גלייַך צווישן סטודענטן

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

קאַמפּלעקסיטי אַנאַליסיס פֿאַר מאַקסימום נומער פון טשאָקלאַץ צו זיין פונאנדערגעטיילט גלייַך צווישן סטודענטן  

צייט קאַמפּלעקסיטי

אָ (N) ווו “N” איז די נומער פון עלעמענטן אין דער מענגע.

זע אויך
נומער פון עקוויוואַלענט דאָמינאָ פּערז לעעטקאָדע סאַלושאַן

ספעיס קאַמפּלעקסיטי

אָ (N) ווו “N” איז די נומער פון עלעמענטן אין דער מענגע.

דערמאָנען