K студенттер арасында бірдей үлестіруге болатын шоколадтардың максималды саны


Күрделілік дәрежесі орта
Жиі кіреді Accenture Adobe Amazon Facebook Фуркиттер
Array Hash

«K оқушыларына бірдей үлестірілетін шоколадтың ең көп саны» сізге бірнеше шоколад салынған n қорап берілгенін айтады. K оқушы бар делік. Тапсырма - шоколадтардың санын максималды түрде k студенттер арасында, қатардағы қораптарды таңдау арқылы бірдей үлестіру. Қораптар 1-ден n-ге дейінгі сандардан тұратын қатарда болады деп болжауға болады. міндет - шоколадты k оқушыға бірдей үлестіре алатын қораптар тобын таңдау. Берілген қораптар массив ретінде қарастырылуы мүмкін және arr [i] ондағы шоколад санын i'th индексі жағдайында көрсете алады.

мысал

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] ретінде орнатыңыз, [0] қосындысының бірінші мәні arr [0] сияқты болу керек дегенді білдіреді. Жүріп өткен кезде массив, біз [i] және қосынды [i-1] қосамыз және мәнді [i] қосындыға сақтаймыз, осылайша біз жиым мен қосындының алдыңғы индекстер элементінің мәндерін қосамыз. Онда жиынтық массивтің мәндері болады.

Оған мысал келтірейік:

мысал

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

қосынды [0] = arr [0] = 1.

қосынды [1] = arr [i] + қосынды [i-1] = 6,

қосынды [2] = arr [i] + sum [i-1] = 9, оны жалғастыра отырып, қосынды массивінде келесі мәндерге ие боламыз.

қосынды [] = {1, 6, 9, 15, 25, 26}.

Біз [i]% k қосындысын алып, жиымды тағы да айналып өтеміз. Темптің 0-ге тең екендігін тексереміз, бірақ ол жоқ, сондықтан картада бұл мән жоқ екенін тексереміз, оны картаға ағымдағы индекспен қоямыз. Сонымен, картада бізде (1,0) бар.

Келесі 6 санын алып, уақытша [i]% k қосындысын тексеру 0-ге тең, сондықтан нәтижені қазір жаңартамыз. Нәтижесінде 6 болады.

Келесі элемент 9 және 15 болар еді, бұл қалыпта екеуінің де модулі 3-ке тең, сондықтан 0-ке дейін, нәтиже 15-ке тең болады. Келесі сан 15, бізде қазір 25 сияқты темп-р бар. басқа жағдайға. Бірақ бізде картаға 1 енгізілген. Сонымен, біз оның мәнін аламыз және ол 1-ге тең, өйткені біз 0 мен 1 картаға сақтадық. Сонда біз [i] -sum [0] қосындысын анықтаймыз, және 0 болады, осы санға дейін жаңартыңыз.

Тағы бір нөмірге барғаннан кейін бізде жауап 24-те болады. Соңында біз 24/3 яғни 8-ге ораламыз. Бұл біздің соңғы жауабымыз болады.

K студенттер арасында бірдей үлестіруге болатын шоколадтардың максималды саны

Іске асыру

С ++ бағдарламасы, шоколадтардың максималды саны, 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 студенттер арасында бірдей таратылатын шоколадтың максималды санына арналған 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) қайда «N» - бұл массивтегі элементтер саны.

Ғарыштың күрделілігі

O (N) қайда «N» - бұл массивтегі элементтер саны.

анықтамалық