k人の学生に均等に配布されるチョコレートの最大数


難易度 ミディアム
よく聞かれる アクセンチュア Adobe Amazon (アマゾン) Facebook フォーカイテス
配列 ハッシュ

「k人の生徒に均等に配布されるチョコレートの最大数」には、チョコレートが入ったn個の箱が与えられていると記載されています。 k人の学生がいると仮定します。 タスクは、連続するボックスを選択することにより、k人の学生にチョコレートの最大数を均等に分配することです。 ボックスは1からnまでの数字で構成される行にあると想定できます。 タスクは、k人の生徒に最も多くのチョコレートを均等に配布できるボックスのグループを選択することです。 与えられたボックスは配列と見なすことができ、arr [i]はi番目のインデックスの位置にあるチョコレートの数を表すことができます。

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

k = 3
8

説明: サブ配列5、3、6、10の数字は、k人の生徒に配布できる24個のチョコレートを構成します。 これは、生徒8人あたりXNUMX個のチョコレートを意味します。これは、指定された値の最大値です。

アルゴリズム

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人の生徒に均等に分配するタスクを与えました。 ボックスは基本的にチョコレートの数を表す配列です。 XNUMXつの条件もあります。チョコレートを配布するには、連続するボックスを選択する必要があり、配布を最大化する必要があります。

使用します ハッシュ。 宣言します 地図。 ただし、その前に、指定された配列と同じサイズの空の配列、つまりnを作成します。 値sum [0]をarr [0]の時点で設定します。これは、sum [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)があります。

次の数値6を取得し、sum [i]%kを温度としてチェックすると、0であることがわかったので、結果を更新します。 結果は6になります。

次の要素は9と15になります。このパターンでは、両方とも3を法として0であるため、15までの結果は15になります。次の数値は25で、温度は1になります。 else条件に。 しかし、すでに1つがマップに含まれています。 したがって、0と1をマップに格納したので、その値を取得します。これは0です。 次に、sum [i] -sum [0]を見つけます。これは、24になり、結果をこの数値に更新します。

もう24つの番号にアクセスした後も、24であるため、まだ答えがあります。最後に、3/8、つまりXNUMXを返します。これが最終的な答えになります。

k人の学生に均等に配布されるチョコレートの最大数

製品の導入

k人の学生に均等に配布されるチョコレートの最大数のための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

k人の学生に均等に配布されるチョコレートの最大数のためのJavaプログラム

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) where 「n」 配列の要素数です。

スペースの複雑さ

O(N) where 「n」 配列の要素数です。

参照