შოკოლადის მაქსიმალური რაოდენობა, რომელიც თანაბრად უნდა განაწილდეს k სტუდენტებში


Რთული ტური საშუალო
ხშირად ეკითხებიან Accenture Adobe Amazon Facebook ფურკიტები
Array Hash

”შოკოლადის მაქსიმალური რაოდენობა, რომელიც თანაბრად უნდა განაწილდეს კ სტუდენტებში” აღნიშნავს, რომ თქვენ მოცემულია n ყუთი, რომელშიც არის რამდენიმე შოკოლადი. დავუშვათ, რომ არსებობს k სტუდენტები. ამოცანაა შოკოლადების მაქსიმალური რაოდენობის განაწილება k სტუდენტებში თანაბრად, თანმიმდევრული უჯრების შერჩევით. შეგვიძლია ვივარაუდოთ, რომ ყუთები მწკრივშია და შედგება 1-დან n -მდე რიცხვებისაგან. ამოცანაა შეარჩიოთ ყუთების ჯგუფი, რომელსაც შეუძლია თანაბრად დაარიგოს შოკოლადების უდიდესი რაოდენობა k სტუდენტებს. მოცემული უჯრები შეიძლება ჩაითვალოს მასივად და arr [i] შეიძლება წარმოადგენდეს მასში შოკოლადების რაოდენობას მე –XNUMX ინდექსის პოზიციაზე.

მაგალითი

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], ამ წესით, ჩვენ დავამატებთ მასივის მნიშვნელობებს და 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, მისი გაგრძელებით, თანხის მასივში გვექნება შემდეგი მნიშვნელობები.

ჯამი [] = {1, 6, 9, 15, 25, 26}.

ჩვენ კვლავ გადავკვეთთ მასივს, ავიღებთ ტემპერატურას, როგორც ჯამი [i]% k. ჩვენ შეამოწმებთ არის თუ არა temp ტოლი 0, მაგრამ ეს ასე არ არის, ამიტომ შეამოწმებთ თუ რუკა არ შეიცავს ამ მნიშვნელობას, ჩვენ მას ვაყენებთ მიმდინარე ინდექსთან ერთად რუქაში. ასე რომ, რუკაზე ახლა გვაქვს (1,0).

შემდეგი 6 ნომრის არჩევა და თანხის [i]% k დროებითი შემოწმება, აღმოჩნდა, რომ ახლა 0-ია, ამიტომ შედეგს ახლავე განვაახლებთ. შედეგი იქნება 6.

შემდეგი ელემენტი იქნება 9 და 15, ამ შაბლონში ორივეს 3 მოდული აქვს 0 არის 15, ასე რომ 15 მდე 25 იქნება შედეგი 1. შემდეგი რიცხვი 1 არის, ახლა ჩვენ გვაქვს ტემპი 0. ასე რომ ჩვენ გადავდივართ სხვა მდგომარეობაში. მაგრამ 1 უკვე გვაქვს რუკაზე. ასე რომ, ჩვენ მივიღებთ მის მნიშვნელობას და ეს არის 0, რადგან ჩვენ 0 და 24 შევინახეთ რუკაზე. შემდეგ გავარკვევთ ჯამს [i] -sum [XNUMX], და ეს იქნება XNUMX, ამ რიცხვის განახლების შედეგად.

კიდევ ერთი ნომრის მონახულების შემდეგ, პასუხი კვლავ გვაქვს, რადგან ის არის 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

ჯავა პროგრამა შოკოლადის მაქსიმალური რაოდენობისთვის, რომელიც თანაბრად უნდა განაწილდეს 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 სტუდენტებში

დროის სირთულე

O (n) სადაც "ნ" არის მასივის ელემენტების რაოდენობა.

სივრცის სირთულე

O (n) სადაც "ნ" არის მასივის ელემენტების რაოდენობა.

Reference