حداکثر تعداد شکلات هایی که به طور مساوی بین دانشجویان k توزیع می شود  


سطح دشواری متوسط
اغلب در Accenture خشت آمازون فیس بوک فورکایت
صف مخلوط

"حداکثر تعداد شکلات هایی که به طور مساوی بین دانش آموزان k توزیع می شود" بیان می کند که به شما n جعبه ای داده می شود که دارای برخی شکلات ها است. فرض کنید k دانشجو وجود دارد. وظیفه این است که با انتخاب جعبه های متوالی ، حداکثر تعداد شکلات ها بین دانشجویان k به طور مساوی توزیع شود. می توان فرض کرد که کادرها در یک ردیف متشکل از اعداد از 1 تا n قرار دارند. وظیفه این است که گروهی از جعبه ها را انتخاب کنید که بتواند بیشترین شکلات را برای دانشجویان k به طور مساوی توزیع کند. جعبه های داده شده را می توان به عنوان یک آرایه در نظر گرفت و ar [i] می تواند نشان دهنده تعداد شکلات های موجود در آن در موقعیت شاخص i باشد.

مثال  

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

k = 3
8

شرح: اعداد زیر آرایه 5 ، 3 ، 6 ، 10 24 شکلات را تشکیل می دهند که می توانند بین دانش آموزان k توزیع شوند. این به معنای 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] را از arr تنظیم کنید [0] ، به این معنی که اولین مقدار حاصل از جمع [0] باید با arr [0] برابر باشد. در حالی که عبور از صف، ما arr [i] و sum [i-1] را اضافه خواهیم کرد و مقدار را در sum [i] ذخیره خواهیم کرد ، به این ترتیب ، مقادیر عناصر قبلی آرایه و جمع را جمع خواهیم کرد. مقادیر موجود در آرایه sum را خواهیم داشت.

اجازه دهید مثالی از آن بزنیم:

مثال

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

sum [0] = arr [0] = 1.

sum [1] = arr [i] + sum [i-1] = 6 ،

sum [2] = arr [i] + sum [i-1] = 9 ، با ادامه دادن آن ، مقادیر زیر را در آرایه sum خواهیم داشت.

sum [] = {1 ، 6 ، 9 ، 15 ، 25 ، 26}.

ما دوباره آرایه را رد می کنیم و دما را به عنوان جمع [i]٪ k انتخاب می کنیم. بررسی خواهیم کرد که اگر temp برابر با 0 باشد ، اینگونه نیست ، بنابراین اگر نقشه حاوی این مقدار نباشد ، بررسی خواهیم کرد ، آن را با شاخص فعلی در نقشه قرار خواهیم داد. بنابراین بر روی نقشه ، اکنون (1,0،XNUMX) داریم.

شماره 6 بعدی را بردارید و علامت [i]٪ k را به عنوان دما بررسی کنید ، اکنون 0 بدست آمده است ، بنابراین ما اکنون نتیجه را به روز می کنیم. نتیجه 6 خواهد بود.

عنصر بعدی 9 و 15 خواهد بود ، در این الگو هر دو دارای مدول 3 می باشند 0 است ، بنابراین حداکثر تا 15 نتیجه 15 خواهد بود. عدد بعدی 25 است ، ما اکنون یک دما داریم مانند 1 به شرط دیگر. اما 1 مورد از قبل در نقشه موجود است. بنابراین مقدار 0 و 1 را بدست خواهیم آورد ، زیرا 0 و 0 را در نقشه ذخیره کرده ایم. سپس مقدار [i] -sum [24] را خواهیم فهمید ، و این XNUMX خواهد بود ، نتیجه این شماره به روز می شود.

همچنین مشاهده کنید
دنباله مرتب شده از اندازه 3 را در زمان خطی پیدا کنید

پس از بازدید از یک شماره دیگر ، جواب همچنان 24 است. سرانجام ، ما 24/3 یعنی 8 را برمی گردانیم. این پاسخ نهایی ما خواهد بود.

حداکثر تعداد شکلات هایی که به طور مساوی بین دانشجویان k توزیع می شودسنجاق

پیاده سازی  

برنامه 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 توزیع می شود  

پیچیدگی زمان

O (N) جایی که "n" تعداد عناصر آرایه است.

همچنین مشاهده کنید
تعداد معادل جفت دومینو راه حل کد کد

پیچیدگی فضا

O (N) جایی که "n" تعداد عناصر آرایه است.

ارجاع