Μέγιστος αριθμός σοκολατών που θα διανεμηθούν ίσα μεταξύ των μαθητών k


Επίπεδο δυσκολίας Μέσον
Συχνές ερωτήσεις Accenture πλίθα αμαζόνα Facebook Fourkites
Παράταξη Χασίσι

«Ο μέγιστος αριθμός σοκολατών που θα διανεμηθούν εξίσου στους μαθητές k» δηλώνει ότι σας δίνονται κουτιά που έχουν μερικές σοκολάτες σε αυτό. Ας υποθέσουμε ότι υπάρχουν μαθητές k. Ο στόχος είναι να κατανέμεται εξίσου ο μέγιστος αριθμός σοκολατών στους μαθητές, επιλέγοντας διαδοχικά κουτιά. Μπορούμε να υποθέσουμε ότι τα πλαίσια είναι σε σειρά που αποτελείται από αριθμούς από 1 έως n. ο στόχος είναι να επιλέξετε μια ομάδα κουτιών που μπορούν να διανείμουν τον μεγαλύτερο αριθμό σοκολατών στους μαθητές. Τα κουτιά που δίνονται μπορούν να θεωρηθούν ως πίνακας και το arr [i] μπορεί να αντιπροσωπεύει τον αριθμό σοκολατών σε αυτό στη θέση του ευρετηρίου.

Παράδειγμα

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 ).

εξήγηση

Έχουμε δώσει ένα καθήκον να κατανείμουμε τις μέγιστες σοκολάτες στους μαθητές. Το κουτί είναι βασικά ένας πίνακας που αντιπροσωπεύει τον αριθμό των σοκολατών. Ένας όρος είναι επίσης εκεί, πρέπει να επιλέξουμε διαδοχικά κουτιά για να διανείμουμε σοκολάτες και η διανομή θα πρέπει να μεγιστοποιηθεί.

Θα χρησιμοποιήσουμε κατακερματισμός. Θα δηλώσουμε ένα Χάρτης. Αλλά, πριν από αυτό θα δημιουργήσουμε έναν κενό πίνακα, του ίδιου μεγέθους με τον δεδομένο πίνακα, δηλαδή n. Ορίστε το άθροισμα τιμής [0] από arr [0], σημαίνει ότι η πρώτη τιμή του αθροίσματος [0] πρέπει να είναι ίδια με το arr [0]. Ενώ διασχίζουμε το παράταξη, θα προσθέσουμε το arr [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] + άθροισμα [i-1] = 9, συνεχίζοντας το, θα έχουμε τις ακόλουθες τιμές στον πίνακα αθροίσματος.

άθροισμα [] = {1, 6, 9, 15, 25, 26}.

Θα διασχίσουμε ξανά τον πίνακα, παίρνοντας τη θερμοκρασία ως άθροισμα [i]% k. Θα ελέγξουμε αν η θερμοκρασία είναι ίση με 0, αλλά όχι, οπότε θα ελέγξουμε εάν ο χάρτης δεν περιέχει αυτήν την τιμή, θα το βάλουμε με τον τρέχοντα ευρετήριο σε έναν χάρτη. Έτσι, στο χάρτη, έχουμε (1,0) τώρα.

Η παραλαβή του επόμενου αριθμού 6 και ο έλεγχος του αθροίσματος [i]% k ως temp, βρέθηκε να είναι 0 τώρα, οπότε θα ενημερώσουμε το αποτέλεσμα τώρα. Το αποτέλεσμα θα ήταν 6.

Το επόμενο στοιχείο θα ήταν 9 και 15, σε αυτό το μοτίβο και οι δύο έχουν modulo έως 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 για μέγιστο αριθμό σοκολατών που κατανέμονται ισότιμα ​​μεταξύ των μαθητών

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

Ανάλυση πολυπλοκότητας για τον μέγιστο αριθμό σοκολατών που κατανέμονται ισότιμα ​​μεταξύ των μαθητών

Χρόνος πολυπλοκότητας

O (n) όπου «Ν» είναι ο αριθμός των στοιχείων στον πίνακα.

Διαστημική πολυπλοκότητα

O (n) όπου «Ν» είναι ο αριθμός των στοιχείων στον πίνακα.

Αναφορά