د چاکلیټ اعظمي شمیر چې د زده کونکو په مینځ کې مساوي ویشل شي


مشکل کچه منځني
په مکرر ډول دننه پوښتل کیږي Accenture ایڈوب ترلاسه کړئ Amazon فیسبوک څلورکیټونه
پیشه هاش

"د چاکلیټ اعظمي شمیر چې د زده کونکو په مینځ کې مساوي توزیع کیږي" په ګوته کوي چې تاسو ته n بکس ورکول کیږي چې پدې کې یو څه چاکلیټونه لري. فرض کړئ چې د زده کونکي زده کونکي شتون لري. دنده دا ده چې د k زده کونکو ترمنځ په مساوي ډول د پرله پسې بکسونو په غوره کولو سره د چکلیټونو زیات شمیر توزیع کړئ. موږ دا فرض کولی شو چې بکسونه په قطار کې دي چې له 1 څخه تر n پورې شمیرې لري. دنده دا ده چې د بکسونو ګروپ وټاکئ چې کولی شي د زده کونکو زده کونکو ته خورا ډیر شمیر چاکلیټونه توزیع کړي. بکسونه چې ورکړل شوي دي د صف په توګه په پام کې نیول کیدی شي او آر [i] کولی شي په هغې کې د چاکلیټونو شمیر د Ith شاخص کې استازیتوب وکړي.

بېلګه

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

تشریح

موږ د k زده کونکو ترمنځ په مساوي توګه د چاکلیټونو ویشلو ته دنده سپارلې ده. بکس اساسا یو صف دی چې د چاکلیټونو نمایندګي کوي. یو شرط هم شتون لري ، موږ باید د چاکلیټونو توزیع لپاره پرله پسې بکسونه غوره کړو او توزیع باید اعظمي شي.

موږ کارولو ته ځو ټوپونه. موږ به اعالن کړو نقشه. مګر ، مخکې لدې چې موږ به د ورکړل شوي صفونو په ورته اندازې خالي تشې رامینځته کړو ، دا n ده. د ارزښت شمیره [0] د آرر په توګه تنظیم کړئ [0] ، پدې معنی چې د لومړي ارزښت ارزښت [0] باید د تیر په څیر ورته وي [0]. د سور، موږ به آر آر [i] او لنډیز [i-1] اضافه کړو او ارزښت په مجموع کې وساتو [i] ، پدې توګه ، موږ به د صف او پخوانیو شاخصونو عنصر ارزښت اضافه کړو. موږ به پدې برخه کې ارزښتونه ولرو.

راځئ چې د دې مثال واخلو:

بېلګه

تیر [] = {1 ، 5 ، 3 ، 6 ، 10 ، 1} ، k = 3

جمع [0] = تیر [0] = 1.

جمع [1] = آرر [i] + جمع [i-1] = 6 ،

جمع [2] = آر آر [i] + جمع [i-1] = 9 ، د دې په دوام ، موږ به د لنډیز په لړ کې لاندې ارزښتونه ولرو.

جمع [] = {1 ، 6 ، 9 ، 15 ، 25 ، 26}.

موږ به بیا له تیر څخه تیر کړو ، لنډمهاله ټیم غوره کړو [i]٪ k. موږ به وګورو چې ټیمپ د 0 سره مساوي دی ، مګر دا ندی ، نو موږ به وګورو چې ایا نقشه دا ارزښت نلري ، موږ به دا په نقشه کې د اوسني شاخص سره ځای په ځای کړو. نو په نقشه کې ، موږ اوس (1,0،XNUMX) لرو.

د 6 شمیره پورته کول او د ټیم په توګه [i]٪ k جمع کول ، دا اوس 0 معلومیږي ، نو موږ به یې همدا اوس تازه کړو. پایلې به یې 6 وي.

راتلونکی عنصر به 9 او 15 وي ، پدې ب inه کې دواړه له 3 څخه تر 0 پورې 15 دي ، نو تر 15 پورې ، پایله به یې 25 وي. راتلونکی شمیره 1 ده ، موږ اوس د 1 په څیر یو ټیم لرو. نو موږ به ځو بل حالت ته. مګر موږ 0 دمخه په نقشه کې لرو. نو موږ به د دې ارزښت ترلاسه کړو او دا 1 دی ، لکه څنګه چې موږ په نقشه کې 0 او 0 ذخیره کړې. بیا به موږ مجموعه ومومم [i] -سم [24] ، او دا به XNUMX وي ، پدې شمیره کې د پایلو تازه کول.

د یو بل شمیر لیدلو وروسته ، موږ لاهم ځواب لرو لکه څنګه چې 24 دی. په نهایت کې ، موږ به 24/3 بیرته راوړو چې دا 8 دی. دا به زموږ وروستی ځواب وي.

د چاکلیټ اعظمي شمیر چې د زده کونکو په مینځ کې مساوي ویشل شي

تطبیق

د چکلیټونو زیات شمیر لپاره C ++ برنامه ترڅو د K زده کونکو ترمنځ په مساوي ډول وویشل شي

#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

د چاکلیټونو اعظمي شمیر لپاره جاوا برنامې باید د k زده کونکو ترمنځ په مساوي ډول وویشل شي

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

د چاکلیټ اعظمي شمیر لپاره د پیچلتیا تحلیل ترڅو د K زده کونکو ترمنځ مساوي وویشل شي

د وخت پیچلتیا

اې (N) هلته "n" په صف کې د عناصرو شمیر دی.

د ځای پیچلتیا

اې (N) هلته "n" په صف کې د عناصرو شمیر دی.

ماخذ