ಕೆ ವಿದ್ಯಾರ್ಥಿಗಳಲ್ಲಿ ಸಮಾನವಾಗಿ ವಿತರಿಸಬೇಕಾದ ಗರಿಷ್ಠ ಸಂಖ್ಯೆಯ ಚಾಕೊಲೇಟ್‌ಗಳು


ತೊಂದರೆ ಮಟ್ಟ ಮಧ್ಯಮ
ಆಗಾಗ್ಗೆ ಕೇಳಲಾಗುತ್ತದೆ ಅಸೆಂಚರ್ ಅಡೋಬ್ ಅಮೆಜಾನ್ ಫೇಸ್ಬುಕ್ ಫೋರ್‌ಕೈಟ್‌ಗಳು
ಅರೇ ಹ್ಯಾಶ್

"ಕೆ ವಿದ್ಯಾರ್ಥಿಗಳಲ್ಲಿ ಸಮಾನವಾಗಿ ವಿತರಿಸಬೇಕಾದ ಗರಿಷ್ಠ ಸಂಖ್ಯೆಯ ಚಾಕೊಲೇಟ್‌ಗಳು" ನಿಮಗೆ ಕೆಲವು ಪೆಟ್ಟಿಗೆಗಳನ್ನು ಹೊಂದಿರುವ ಎನ್ ಪೆಟ್ಟಿಗೆಗಳನ್ನು ನೀಡಲಾಗಿದೆ ಎಂದು ಹೇಳುತ್ತದೆ. ಕೆ ವಿದ್ಯಾರ್ಥಿಗಳು ಇದ್ದಾರೆ ಎಂದು ಭಾವಿಸೋಣ. ಸತತ ಪೆಟ್ಟಿಗೆಗಳನ್ನು ಆರಿಸುವ ಮೂಲಕ ಕೆ ವಿದ್ಯಾರ್ಥಿಗಳಲ್ಲಿ ಗರಿಷ್ಠ ಸಂಖ್ಯೆಯ ಚಾಕೊಲೇಟ್‌ಗಳನ್ನು ಸಮಾನವಾಗಿ ವಿತರಿಸುವುದು ಇದರ ಕಾರ್ಯವಾಗಿದೆ. ಪೆಟ್ಟಿಗೆಗಳು 1 ರಿಂದ n ವರೆಗಿನ ಸಂಖ್ಯೆಗಳನ್ನು ಒಳಗೊಂಡಿರುವ ಸಾಲಿನಲ್ಲಿವೆ ಎಂದು ನಾವು can ಹಿಸಬಹುದು. ಕೆ ವಿದ್ಯಾರ್ಥಿಗಳಿಗೆ ಸಮನಾಗಿ ಹೆಚ್ಚಿನ ಸಂಖ್ಯೆಯ ಚಾಕೊಲೇಟ್‌ಗಳನ್ನು ವಿತರಿಸಬಹುದಾದ ಪೆಟ್ಟಿಗೆಗಳ ಗುಂಪನ್ನು ಆಯ್ಕೆ ಮಾಡುವುದು ಕಾರ್ಯವಾಗಿದೆ. ನೀಡಲಾದ ಪೆಟ್ಟಿಗೆಗಳನ್ನು ಒಂದು ಶ್ರೇಣಿಯೆಂದು ಪರಿಗಣಿಸಬಹುದು ಮತ್ತು ಅರ್ [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 ).

ವಿವರಣೆ

ಕೆ ವಿದ್ಯಾರ್ಥಿಗಳಲ್ಲಿ ಗರಿಷ್ಠ ಚಾಕೊಲೇಟ್‌ಗಳನ್ನು ಸಮಾನವಾಗಿ ವಿತರಿಸುವ ಕಾರ್ಯವನ್ನು ನಾವು ನೀಡಿದ್ದೇವೆ. ಬಾಕ್ಸ್ ಮೂಲತಃ ಚಾಕೊಲೇಟ್‌ಗಳ ಸಂಖ್ಯೆಯನ್ನು ಪ್ರತಿನಿಧಿಸುವ ಒಂದು ಶ್ರೇಣಿಯಾಗಿದೆ. ಒಂದು ಷರತ್ತು ಸಹ ಇದೆ, ಚಾಕೊಲೇಟ್‌ಗಳನ್ನು ವಿತರಿಸಲು ನಾವು ಸತತ ಪೆಟ್ಟಿಗೆಗಳನ್ನು ಆರಿಸಬೇಕು ಮತ್ತು ವಿತರಣೆಯನ್ನು ಗರಿಷ್ಠಗೊಳಿಸಬೇಕು.

ನಾವು ಬಳಸಲಿದ್ದೇವೆ ಹ್ಯಾಶಿಂಗ್. ನಾವು ಎ ಎಂದು ಘೋಷಿಸುತ್ತೇವೆ ನಕ್ಷೆ. ಆದರೆ, ಅದಕ್ಕೂ ಮೊದಲು ನಾವು ಖಾಲಿ ರಚನೆಯನ್ನು ರಚಿಸುತ್ತೇವೆ, ಕೊಟ್ಟಿರುವ ರಚನೆಯ ಗಾತ್ರದ, ಅಂದರೆ n. ಮೌಲ್ಯದ ಮೊತ್ತವನ್ನು [0] ಅರ್ [0] ರಂತೆ ಹೊಂದಿಸಿ, ಅಂದರೆ ಮೊತ್ತದ ಮೊದಲ ಮೌಲ್ಯ [0] ಅರ್ [0] ಗೆ ಸಮನಾಗಿರಬೇಕು. ಸಂಚರಿಸುವಾಗ ಸರಣಿ, ನಾವು arr [i] ಮತ್ತು sum [i-1] ಅನ್ನು ಸೇರಿಸುತ್ತೇವೆ ಮತ್ತು ಮೌಲ್ಯವನ್ನು ಮೊತ್ತವಾಗಿ ಸಂಗ್ರಹಿಸುತ್ತೇವೆ [i], ಈ ರೀತಿಯಾಗಿ, ನಾವು ಒಂದು ಶ್ರೇಣಿಯ ಮೌಲ್ಯಗಳನ್ನು ಮತ್ತು ಮೊತ್ತದ ಹಿಂದಿನ ಸೂಚ್ಯಂಕ ಅಂಶವನ್ನು ಸೇರಿಸುತ್ತೇವೆ. ನಾವು ಅದರಲ್ಲಿ ಮೌಲ್ಯಗಳನ್ನು ಹೊಂದಿರುತ್ತೇವೆ.

ನಾವು ಅದರ ಉದಾಹರಣೆಯನ್ನು ತೆಗೆದುಕೊಳ್ಳೋಣ:

ಉದಾಹರಣೆ

arr [] = {1, 5, 3, 6, 10, 1}, k = 3

ಮೊತ್ತ [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 ಎಂದು ತೆಗೆದುಕೊಳ್ಳುತ್ತೇವೆ. ಟೆಂಪ್ 0 ಕ್ಕೆ ಸಮನಾಗಿದೆಯೇ ಎಂದು ನಾವು ಪರಿಶೀಲಿಸುತ್ತೇವೆ, ಆದರೆ ಅದು ಅಲ್ಲ, ಆದ್ದರಿಂದ ನಕ್ಷೆಯು ಈ ಮೌಲ್ಯವನ್ನು ಹೊಂದಿಲ್ಲವೇ ಎಂದು ನಾವು ಪರಿಶೀಲಿಸುತ್ತೇವೆ, ನಾವು ಅದನ್ನು ಪ್ರಸ್ತುತ ಸೂಚ್ಯಂಕದೊಂದಿಗೆ ನಕ್ಷೆಯಲ್ಲಿ ಇಡುತ್ತೇವೆ. ಆದ್ದರಿಂದ ನಕ್ಷೆಯಲ್ಲಿ, ನಾವು ಈಗ (1,0) ಹೊಂದಿದ್ದೇವೆ.

ಮುಂದಿನ ಸಂಖ್ಯೆ 6 ಅನ್ನು ಎತ್ತಿಕೊಂಡು ಮೊತ್ತವನ್ನು [i]% k ಅನ್ನು ಟೆಂಪ್ ಆಗಿ ಪರಿಶೀಲಿಸುವುದು ಈಗ 0 ಎಂದು ಕಂಡುಬಂದಿದೆ, ಆದ್ದರಿಂದ ನಾವು ಈಗ ಫಲಿತಾಂಶವನ್ನು ನವೀಕರಿಸುತ್ತೇವೆ. ಫಲಿತಾಂಶ 6 ಆಗಿರುತ್ತದೆ.

ಮುಂದಿನ ಅಂಶವು 9 ಮತ್ತು 15 ಆಗಿರುತ್ತದೆ, ಈ ಮಾದರಿಯಲ್ಲಿ ಎರಡೂ ಮಾಡ್ಯುಲೋ 3 ರಿಂದ 0 ಆಗಿರುತ್ತದೆ, ಆದ್ದರಿಂದ 15 ರವರೆಗೆ, ಫಲಿತಾಂಶವು 15 ಆಗಿರುತ್ತದೆ. ಮುಂದಿನ ಸಂಖ್ಯೆ 25, ನಾವು ಈಗ 1 ರಂತೆ ಟೆಂಪ್ ಹೊಂದಿದ್ದೇವೆ. ಆದ್ದರಿಂದ ನಾವು ಜಿಗಿಯುತ್ತೇವೆ ಬೇರೆ ಸ್ಥಿತಿಗೆ. ಆದರೆ ನಾವು ಈಗಾಗಲೇ 1 ಅನ್ನು ನಕ್ಷೆಯಲ್ಲಿ ಹೊಂದಿದ್ದೇವೆ. ಆದ್ದರಿಂದ ನಾವು ಅದರ ಮೌಲ್ಯವನ್ನು ಪಡೆಯುತ್ತೇವೆ ಮತ್ತು ಅದು 0 ಮತ್ತು ನಾವು 1 ಮತ್ತು 0 ಅನ್ನು ನಕ್ಷೆಯಲ್ಲಿ ಸಂಗ್ರಹಿಸಿದ್ದೇವೆ. ನಂತರ ನಾವು [i] -ಸಮ್ [0] ಮೊತ್ತವನ್ನು ಕಂಡುಕೊಳ್ಳುತ್ತೇವೆ ಮತ್ತು ಅದು 24 ಆಗಿರುತ್ತದೆ, ಈ ಸಂಖ್ಯೆಗೆ ಅನುಗುಣವಾಗಿ ನವೀಕರಿಸಿ.

ಇನ್ನೂ ಒಂದು ಸಂಖ್ಯೆಗೆ ಭೇಟಿ ನೀಡಿದ ನಂತರ, ಅದು 24 ರಂತೆ ನಮ್ಮಲ್ಲಿ ಇನ್ನೂ ಉತ್ತರವಿದೆ. ಅಂತಿಮವಾಗಿ, ನಾವು 24/3 ಅಂದರೆ 8 ಎಂದು ಹಿಂದಿರುಗಿಸುತ್ತೇವೆ. ಇದು ನಮ್ಮ ಅಂತಿಮ ಉತ್ತರವಾಗಿರುತ್ತದೆ.

ಕೆ ವಿದ್ಯಾರ್ಥಿಗಳಲ್ಲಿ ಸಮಾನವಾಗಿ ವಿತರಿಸಬೇಕಾದ ಗರಿಷ್ಠ ಸಂಖ್ಯೆಯ ಚಾಕೊಲೇಟ್‌ಗಳು

ಅನುಷ್ಠಾನ

ಕೆ ವಿದ್ಯಾರ್ಥಿಗಳಲ್ಲಿ ಸಮಾನವಾಗಿ ವಿತರಿಸಬೇಕಾದ ಗರಿಷ್ಠ ಸಂಖ್ಯೆಯ ಚಾಕೊಲೇಟ್‌ಗಳಿಗಾಗಿ ಸಿ ++ ಪ್ರೋಗ್ರಾಂ

#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

ಕೆ ವಿದ್ಯಾರ್ಥಿಗಳಲ್ಲಿ ಸಮಾನವಾಗಿ ವಿತರಿಸಬೇಕಾದ ಗರಿಷ್ಠ ಸಂಖ್ಯೆಯ ಚಾಕೊಲೇಟ್‌ಗಳ ಸಂಕೀರ್ಣತೆ ವಿಶ್ಲೇಷಣೆ

ಸಮಯ ಸಂಕೀರ್ಣತೆ

ಓ (ಎನ್) ಅಲ್ಲಿ “ಎನ್” ರಚನೆಯ ಅಂಶಗಳ ಸಂಖ್ಯೆ.

ಬಾಹ್ಯಾಕಾಶ ಸಂಕೀರ್ಣತೆ

ಓ (ಎನ್) ಅಲ್ಲಿ “ಎನ್” ರಚನೆಯ ಅಂಶಗಳ ಸಂಖ್ಯೆ.

ರೆಫರೆನ್ಸ್