K සිසුන් අතර සමානව බෙදා හැරිය යුතු උපරිම චොකලට් සංඛ්‍යාව  


දුෂ්කරතා මට්ටම මධ්යම
නිතර අසනු ලැබේ ඇක්සෙන්චර් ඇෙබෝ ඇමේසන් ෆේස්බුක් ෆෝකයිට්
අරා හැෂ්

“K සිසුන් අතර සමානව බෙදා හැරිය යුතු උපරිම චොකලට් සංඛ්‍යාව” සඳහන් කරන්නේ ඔබට චොකලට් කිහිපයක් ඇති පෙට්ටි n ලබා දී ඇති බවයි. K සිසුන් සිටී යැයි සිතමු. කර්තව්යය වන්නේ අඛණ්ඩ පෙට්ටි තෝරා ගැනීමෙන් k සිසුන් අතර උපරිම චොකලට් සංඛ්යාව සමානව බෙදා හැරීමයි. පෙට්ටි 1 සිට n දක්වා සංඛ්‍යා වලින් සමන්විත පේළියක ඇතැයි අපට උපකල්පනය කළ හැකිය. කර්තව්‍යය වන්නේ k සිසුන්ට වැඩි වශයෙන් චොකලට් බෙදා හැරිය හැකි පෙට්ටි සමූහයක් තෝරා ගැනීමයි. ලබා දී ඇති පෙට්ටි අරාව ලෙස සැලකිය හැකි අතර අර [i] 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 ).

පැහැදිලි කිරීම  

K සිසුන් අතර උපරිම චොකලට් සමානව බෙදා හැරීමේ කාර්යයක් අප විසින් ලබා දී ඇත. කොටුව මූලික වශයෙන් චොකලට් ගණන නියෝජනය කරන අරාවකි. එක් කොන්දේසියක් ද තිබේ, අපි චොකලට් බෙදා හැරීම සඳහා අඛණ්ඩ පෙට්ටි තෝරා ගත යුතු අතර බෙදා හැරීම උපරිම කළ යුතුය.

මෙයද බලන්න
දත්ත ව්‍යුහය සැලසුම් කිරීම

අපි පාවිච්චි කරන්නයි යන්නේ හැෂිං. අපි අ සිතියම. නමුත්, ඊට පෙර අපි ලබා දී ඇති අරාව හා සමාන ප්‍රමාණයේ හිස් අරාවක් නිර්මාණය කරමු. Ar [0] හි අගය [0] ලෙස සකසන්න, එයින් අදහස් වන්නේ එකතුවෙහි පළමු අගය [0] arr [0] ට සමාන විය යුතු බවයි. ගමන් කරන අතරතුර අරාව, අපි ar [i] සහ sum [i-1] එකතු කර අගය [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 තෝරාගෙන [k]% k තාවකාලික ලෙස පරික්ෂා කිරීම දැන් 0 බව සොයාගෙන ඇත, එබැවින් අපි දැන් ප්‍රති result ලය යාවත්කාලීන කරන්නෙමු. ප්‍රති ult ලය 6 ක් වනු ඇත.

ඊලඟ මූලද්‍රව්‍යය 9 සහ 15 වනු ඇත, මෙම රටාවේ දෙකම මොඩියුලෝ 3 සිට 0 දක්වා වේ, එබැවින් 15 දක්වා, එහි ප්‍රති ant ලය 15 ක් වනු ඇත. ඊළඟ අංකය 25 වේ, අපට දැන් 1 වැනි තාවකාලිකයක් ඇත. අනෙක් තත්වයට. නමුත් අපට දැනටමත් 1 ක් සිතියමට ඇත. එබැවින් අපි 0 සහ 1 සිතියමෙහි ගබඩා කර ඇති බැවින් එහි වටිනාකම අපට ලැබෙනු ඇත. එවිට අපි [i] -sum [0] එකතුව සොයා ගනිමු, එය 0 ක් වනු ඇත, මෙම අංකයට ප්‍රති update ලයක් ලෙස යාවත්කාලීන කරන්න.

මෙයද බලන්න
රේඛීය වේලාවේ 3 ප්‍රමාණයේ අනුපිළිවෙලක් සොයා ගන්න

තවත් එක් අංකයකට පිවිසීමෙන් පසුව, එය තවමත් 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

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 සිසුන් අතර සමානව බෙදා හැරිය යුතු උපරිම චොකලට් සංඛ්‍යාව සඳහා සංකීර්ණතා විශ්ලේෂණය  

කාල සංකීර්ණත්වය

සාමාන්ය (n) එහිදී “N” යනු අරාවෙහි ඇති මූලද්‍රව්‍ය ගණන වේ.

මෙයද බලන්න
සමාන ඩොමිනෝ යුගල ලීට්කෝඩ් විසඳුම

අභ්‍යවකාශ සංකීර්ණතාව

සාමාන්ය (n) එහිදී “N” යනු අරාවෙහි ඇති මූලද්‍රව්‍ය ගණන වේ.

විමර්ශන