Շոկոլադների առավելագույն քանակը, որը հավասարաչափ կբաշխվի k ուսանողների շրջանում


Դժվարության մակարդակ Միջին
Հաճախակի հարցնում են Accenture 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 ենթաշարքերի թվերը կազմում են 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: Սահմանել [0] արժեքի գումարը arr- ի [0] դրությամբ, նշանակում է [0] գումարի առաջին արժեքը պետք է լինի նույնը, ինչ arr [0]: Մինչդեռ անցնելիս դասավորություն, մենք գումարելու ենք arr [i] և sum [i-1] և արժեքը կպահպանենք sum [i], այս եղանակով մենք գումարելու ենք զանգվածի և գումարի նախորդ ինդեքսների տարրի արժեքները: Մենք կունենանք արժեքները դրա զանգվածի զանգվածում:

Եկեք դրա օրինակ վերցնենք.

Օրինակ

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 [] = {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-ը և 0-ը: Դրանից հետո մենք կիմանանք [i] -sum [0] գումարը, և դա կլինի 24-ը, այս թվի արդյունքում ստացված թարմացումը:

Եվս մեկ համար այցելելուց հետո մենք դեռ պատասխան ունենք, քանի որ այն 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 ուսանողների շրջանում

Timeամանակի բարդություն

O (n) որտեղ «Ն» զանգվածում տարրերի քանակն է:

Տիեզերական բարդություն

O (n) որտեղ «Ն» զանգվածում տարրերի քանակն է:

Մանրամասն