Максимальное количество шоколадных конфет, которое должно быть распределено поровну между k учениками  


Сложный уровень средний
Часто спрашивают в Accenture саман Амазонка Facebook Фуркиты
массив Hash

«Максимальное количество шоколадных конфет, которое должно быть равномерно распределено между k учениками» означает, что вам дается n коробок, в которых есть несколько конфет. Предположим, есть k студентов. Задача - распределить максимальное количество шоколадных конфет между k учениками поровну, выбрав последовательные коробки. Можно считать, что ящики стоят в ряд, состоящий из чисел от 1 до n. задача состоит в том, чтобы выбрать группу коробок, в которой можно равномерно распределить наибольшее количество шоколадных конфет среди k учеников. Указанные коробки можно рассматривать как массив, а arr [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. Установите значение sum [0] как arr [0], это означает, что первое значение sum [0] должно быть таким же, как arr [0]. При прохождении массив, мы будем складывать arr [i] и sum [i-1] и сохранять значение в sum [i], таким образом, мы будем складывать значения массива и предыдущего элемента indexes sum. У нас будут значения в этом массиве сумм.

Давайте возьмем пример:

Пример

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

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

сумма [1] = arr [i] + сумма [i-1] = 6,

sum [2] = arr [i] + sum [i-1] = 9, продолжая его, мы получим следующие значения в массиве sum.

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

Мы снова пройдем по массиву, набрав темп как sum [i]% k. Мы проверим, равно ли temp 0, но это не так, поэтому мы проверим, не содержит ли карта этого значения, мы поместим его с текущим индексом на карту. Итак, на карте у нас есть (1,0).

Если взять следующее число 6 и проверить сумму [i]% k как временную, оказывается, что она равна 0, поэтому мы обновим результат сейчас. Результатом будет 6.

Следующим элементом будет 9 и 15, в этом шаблоне оба имеют модуль до 3, равный 0, поэтому до 15 результат будет 15. Следующее число - 25, у нас теперь временная температура, равная 1. Итак, мы перейдем к условию else. Но у нас уже есть 1 на карте. Таким образом, мы получим его значение, равное 0, поскольку мы сохранили 1 и 0 в карте. Затем мы найдем сумму [i] -sum [0], которая будет равна 24, обновим результат до этого числа.

Смотрите также
Найдите отсортированную подпоследовательность размера 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

Программа на Java для максимального количества шоколадных конфет, которое будет равномерно распределено между 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 учениками  

Сложность времени

О (п) в котором «Н» это количество элементов в массиве.

Смотрите также
Количество эквивалентных домино-пар Решение Leetcode

Космическая сложность

О (п) в котором «Н» это количество элементов в массиве.

Справка