Максималан број чоколада које ће се поделити подједнако међу к ученика


Ниво тешкоће Средњи
Често питани у Аццентуре адобе амазонка фацебоок Фоуркитес
Ред Хасх

„Максималан број чоколада које треба поделити подједнако међу к ученика“ наводи да ћете добити н кутија у којима је неколико чоколада. Претпоставимо да има к ученика. Задатак је поделити максималан број чоколада међу к ученика подједнако, избором узастопних кутија. Можемо претпоставити да су оквири у низу који се састоје од бројева од 1 до н. задатак је одабрати групу кутија које могу поделити највећи број чоколада равноправно к ученицима. Дате кутије се могу сматрати низом, а арр [и] може представљати број чоколада у њему на месту и-тог индекса.

Пример

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

k = 3
8

objašnjenje: Бројеви из низа 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]. Током обиласка поредак, додаћемо арр [и] и сум [и-1] и сачувати вредност у сум [и], на овај начин ћемо збрајати вредности низа и претходног елемента сума. У њему ћемо имати вредности сум арраи.

Узмимо пример за то:

Пример

арр [] = {1, 5, 3, 6, 10, 1}, к = 3

сума [0] = арр [0] = 1.

сума [1] = арр [и] + сума [и-1] = 6,

сум [2] = арр [и] + сум [и-1] = 9, настављајући га, имаћемо следеће вредности у пољу сум.

сума [] = {1, 6, 9, 15, 25, 26}.

Поново ћемо прећи низ, узимајући темп као сум [и]% к. Проверићемо да ли је темп једнака 0, али није, па ћемо проверити да ли карта садржи ову вредност, поставићемо је са тренутним индексом на мапу. Дакле, на мапи имамо (1,0) сада.

Узети следећи број 6 и проверити суму [и]% к као привремену температуру, сада је 0, па ћемо сада ажурирати резултујућу. Резултат би био 6.

Следећи елемент би био 9 и 15, у овом обрасцу оба имају модул од 3 до 0, тако да до 15, резултанта би била 15. Следећи број је 25, сада имамо темп као 1. Тако ћемо скочити на до другог стања. Али већ имамо 1 на мапи. Тако ћемо добити вредност и то је 0, као што смо 1 и 0 ускладиштили на мапи. Тада ћемо сазнати збир [и] -сум [0], и то ће бити 24, резултујуће ажурирање на овај број.

Након посете још једном броју, и даље имамо одговор као што је 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

Анализа сложености максималног броја чоколада које ће се поделити подједнако међу к ученика

Сложеност времена

Он) где „Н“ је број елемената у низу.

Сложеност простора

Он) где „Н“ је број елемената у низу.

Препорука