k 명의 학생에게 균등하게 분배되는 최대 초콜릿 수


난이도 중급
자주 묻는 질문 Accenture 어도비 벽돌 아마존 페이스북 서비스 포카이트
배열 해시

“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 개의 초콜릿을 의미하며, 이는 주어진 값의 최대 값입니다.

암호알고리즘

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을 생성합니다. arr [0]부터 sum [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.

합계 [1] = arr [i] + 합 [i-1] = 6,

sum [2] = arr [i] + sum [i-1] = 9, 계속하면 합계 배열에 다음 값이 있습니다.

합계 [] = {1, 6, 9, 15, 25, 26}.

우리는 다시 배열을 순회하여 온도를 합계 [i] % k로 선택합니다. temp가 0인지 확인하지만 그렇지 않은지 확인하므로지도에이 값이 포함되어 있지 않은지 확인하고 현재 인덱스를지도에 넣을 것입니다. 이제지도에 (1,0)이 있습니다.

다음 숫자 6을 선택하고 sum [i] % k를 temp로 확인하면 이제 0 인 것으로 확인되었으므로 이제 결과를 업데이트합니다. 결과는 6입니다.

다음 요소는 9와 15가 될 것입니다.이 패턴에서는 둘 다 모듈로 3이 0이므로 15까지, 결과는 15가됩니다. 다음 숫자는 25입니다. 이제 1과 같은 온도를 갖게됩니다. 다른 조건으로. 하지만 이미지도에 1 개가 있습니다. 그래서 우리는지도에 0과 1을 저장했기 때문에 그 값을 얻습니다. 그것은 0입니다. 그런 다음 sum [i] -sum [0]을 알아 내면 24가되고 결과를이 숫자로 업데이트합니다.

번호를 하나 더 방문한 후에도 24는 그대로입니다. 마지막으로 24/3 인 8을 반환합니다. 이것이 최종 답이 될 것입니다.

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) 어디에 "엔" 배열의 요소 수입니다.

공간 복잡성

O (N) 어디에 "엔" 배열의 요소 수입니다.

참고