K વિદ્યાર્થીઓ વચ્ચે સમાનરૂપે વિતરિત થવાની મહત્તમ ચોકલેટ્સની સંખ્યા


મુશ્કેલી સ્તર મધ્યમ
વારંવાર પૂછવામાં આવે છે એક્સેન્ચર એડોબ એમેઝોન ફેસબુક ફોરકાઇટ્સ
અરે હેશ

“કે વિદ્યાર્થીઓ વચ્ચે સમાનરૂપે વિતરિત કરવાની મહત્તમ ચોકલેટ્સ” જણાવે છે કે તમને એન બ nક્સ આપવામાં આવે છે જેમાં તેમાં ચોકલેટ હોય છે. માની લો કે ત્યાં વિદ્યાર્થીઓ છે. સતત બ boxesક્સેસ પસંદ કરીને, કે વિદ્યાર્થીઓમાં સમાનરૂપે ચોકલેટની મહત્તમ સંખ્યા વહેંચવાનું કાર્ય છે. આપણે માની શકીએ કે બક્સ સળંગ 1 માં છે જેની સંખ્યા XNUMX થી n છે. કાર્ય એ છે કે બ boxesક્સના જૂથની પસંદગી કરવી કે જે મોટાભાગની સંખ્યામાં ચોકલેટને કે વિદ્યાર્થીઓ માટે વહેંચી શકે. જે બ boxesક્સેસ આપવામાં આવે છે તે એરે તરીકે ગણી શકાય છે અને એરે [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 વિદ્યાર્થીઓ વચ્ચે મહત્તમ ચોકલેટ સમાનરૂપે વિતરિત કરવાનું કાર્ય આપ્યું છે. બicallyક્સ મૂળભૂત રીતે ચોરેટની સંખ્યાને રજૂ કરતું એક એરે છે. એક શરત પણ છે, ચોકલેટ્સના વિક્ષેપ માટે અમારે સતત બ boxesક્સ પસંદ કરવો આવશ્યક છે અને વિતરણ મહત્તમ થવું જોઈએ.

આપણે વાપરવા જઈ રહ્યા છીએ હેશીંગ. અમે જાહેર કરીશું a નકશો. પરંતુ, તે પહેલાં આપણે ખાલી એરે બનાવીશું, આપેલ એરે જેટલું જ કદ, તે એન. [0] એઆરઆર [0] જેટલું મૂલ્ય સરવાળો સેટ કરો, એટલે કે સરવાળાનું પ્રથમ મૂલ્ય [0] એ આરઆર [0] જેવું હોવું જોઈએ. જ્યારે પસાર એરે, આપણે એરે [i] અને સરવાળો [i-1] ઉમેરીશું અને મૂલ્યનો સરવાળો કરીશું [i], આ રીતે, આપણે એરે અને સરવાળોના અગાઉના સૂચકાંક તત્વોના મૂલ્યો ઉમેરીશું. આપણી પાસે તેમાં સરવાળોના મૂલ્યો હશે.

ચાલો આપણે તેનું ઉદાહરણ લઈએ:

ઉદાહરણ

એરે [] = {1, 5, 3, 6, 10, 1}, k = 3

સરવાળો [0] = અરે [0] = 1.

સરવાળો [1] = અરર [i] + સરવાળો [i-1] = 6,

સરવાળો [2] = એરે [i] + સરવાળો [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] -સમ [0], અને તે 0 ની હશે, પરિણામ આ નંબર પર અપડેટ.

વધુ એક સંખ્યાની મુલાકાત લીધા પછી, અમારી પાસે હજી જવાબ છે કેમ કે તે 24 છે. છેવટે, આપણે 24/3 પરત કરીશું જે 8 છે. આ આપણો અંતિમ જવાબ હશે.

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

ચોકલેટ્સની મહત્તમ સંખ્યા માટે જાવા પ્રોગ્રામ કે વિદ્યાર્થીઓ માટે સમાનરૂપે વિતરિત કરવામાં આવશે

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

ચોકલેટની મહત્તમ સંખ્યા માટે કે જટિલતા વિશ્લેષણ કે વિદ્યાર્થીઓ માટે સમાનરૂપે વિતરિત કરવા

સમય જટિલતા

ઓ (એન) જ્યાં “એન” એરેમાં તત્વોની સંખ્યા છે.

અવકાશ જટિલતા

ઓ (એન) જ્યાં “એન” એરેમાં તત્વોની સંખ્યા છે.

સંદર્ભ