ڪ شاگردن ۾ برابر برابر ورهائڻ لاءِ چاکليٽ جو وڌ کان وڌ انگ


تڪليف جي سطح وچولو
بار بار پڇڻ ۾ Accenture ايڊوب Amazon ڪريو چار چار
ڪيريو هاش

”ڪڪٽرن جو وڌ کان وڌ تعداد برابر هجڻ گهرجي شاگردن ۾“ ٻڌائي ٿو ته توهان کي اين بڪس ڏنا ويندا آهن جن ۾ ڪجهه چاکليٽ هوندي آهي. فرض ڪيو اتي ڪي شاگرد آھن. ڪم ڪ شاگردن ۾ سڀني کان وڌيڪ چاکليٽ جي برابر برابر ورهائڻ آهي ، مسلسل باڪس چونڊڻ. اسان اهو فرض ڪري سگهون ٿا ته بڪس هڪ قطار ۾ آهن 1 کان ن تائين. ڪم ڪرڻ خانن جي هڪ گروپ کي چونڊڻ آهي جيڪو جي شاگردن ۾ تمام گهڻو تعداد ۾ چاڪليٽ ورهائي سگھن. جن خانن کي ڏنو ويو آهي سي ترتيب ڏئي سگھجي ٿو اريو ۽ آرو [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 ).

وضاحت

اسان کي شاگردن ۾ وڌ کان وڌ چاڪليٽ برابر ورهائڻ جو ٽاسڪ ڏنو آهي. دٻي بنيادي طور تي چاڪليٽ جي تعداد جي نمائندگي ڪرڻ لاءِ هڪ صف آهي. هڪ شرط اها به آهي ، اسان کي چاکليٽ ورهائڻ لاءِ لازمي طور تي دٻن کي چونڊڻ گهرجي ۽ ورڇ کي وڌ کان وڌ ڪيو وڃي.

اسان استعمال ٿيڻ وارا آهيون چُڪڻ. اسان اعلان ڪنداسين نقشو. پر ، ان کان اڳ اسان هڪ صف جي خالي صف ٺاهي رهيا آهيون ، انهي سائيز جي جيتري سائيز آهي ، جيڪا اين آهي. arr [0] جي طور تي قيمت سٽ مقرر ڪريو [0] ، مطلب سٿ جي پهرين قيمت [0] ساڳي هجڻ گهرجي arr [0]. جڏهن ته صف، اسان arr [i] ۽ رقم [i-1] شامل ڪندا ۽ قيمت کي sum [i] ۾ شامل ڪندا ، انهي طريقي سان ، اسان هڪ صف ۽ ويل جي اڳوڻي انڊيڪس عنصر جا قدر شامل ڪري رهيا آهيون. اسان وٽ ان جي قيمت موجود هوندي.

اچو ته ان جو هڪ مثال وٺون.

مثال

arr [] = {1 ، 5 ، 3 ، 6 ، 10 ، 1} ، ڪ = 3

سَٽ [0] = arr [0] = 1.

سَٽ [1] = arr [i] + مجموعو [i-1] = 6 ،

sum [2] = arr [i] + sum [i-1] = 9 ، انهي کي جاري رکندي ، اسان کي سميري صف ۾ هيٺيون قدرون هونديون.

رقم [] = {1 ، 6 ، 9 ، 15 ، 25 ، 26}.

اسان صف کي ٻيهر پيچيده سان ترتيب ڏينداسين ، ٽم کڻڻ طور مجموعي طور تي [i]٪ k. اسان چڪاس ڪنداسين ته عارضي 0 جي برابر آهي ، پر اهو ناهي ، تنهن ڪري اسان چڪاس ڪنداسين ته نقشي ۾ اها قيمت شامل ناهي ، اسان نقشي ۾ موجوده انڊيڪس سان رکي رهيا آهيون. تنهنڪري نقشي تي ، اسان وٽ آهي (1,0،XNUMX) هاڻي.

ايندڙ نمبر 6 کي کڻڻ ۽ وقتي طور چڪاس ڪرڻ [i]٪ k کي ڳولھيو ويو ھاڻي 0 کڻو آھي ، تنھنڪري اسين ھاڻي نتيجو ڪندڙ کي تازه ڪاري ڪنداسين. نتيجو 6 هوندو.

ايندڙ عنصر 9 ۽ 15 هوندو ، هن نموني ۾ ٻئي وٽ ماڊليو 3 کان 0 آهن ، تنهن ڪري 15 تائين ، نتيجو 15 ٿي ويندو. ايندڙ نمبر 25 آهي ، اسان وٽ هاڻي جهڙو آهي 1. تنهن ڪري اسين ٽپو ڏينداسين ٻي حالت تي. پر اسان وٽ اڳ ئي 1 نقشي ۾ آهي. تنهنڪري اسان ان جي قيمت حاصل ڪنداسين ۽ اهو آهي 0 ، جئين اسان نقشي ۾ 1 ۽ 0 کي ذخيرو ڪيو. ان کان پوءِ اسان ڳولا ڪندو سسڪو [i] -sum [0] ، ۽ اهو 24 هوندو ، تازه ڪاري هن نمبر جو نتيجو ٿيندو.

هڪ وڌيڪ نمبر گهمڻ کانپوءِ اسان وٽ اڃا به اهو جواب آهي جئين اهو 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

جاوا پروگرام لاءِ وڌ کان وڌ چاکليٽ جي شاگرد لاءِ برابر شاگردن ۾ تقسيم ڪرڻ

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

ڪ شاگردن کان وڌ ۾ وڌ برابر Equاڻيندڙ چکليٽ جي وڌندڙ تعداد جي پيچيدگي جو تجزيو

وقت جي پيچيدگي

اي (ن) جتي “ن” صف ۾ موجود عنصرن جو تعداد آهي.

خلائي پيچيدگي

اي (ن) جتي “ن” صف ۾ موجود عنصرن جو تعداد آهي.

حوالي