К оюутнуудад ижил хэмжээгээр тараах шоколадны дээд хэмжээ


Хэцүү байдлын түвшин Дунд
Байнга асуудаг Accenture Adobe Амазоны Facebook-ийн Фуркайт
Array Хаш

“K оюутны хооронд тэнцүү хэмжээгээр тараагдах шоколадны хамгийн их тоо” гэж танд зарим шоколадтай n хайрцгийг өгөх болно. K оюутан байгаа гэж бодъё. Даалгавар бол дараалсан хайрцгийг сонгон шоколадны тоог хамгийн их тоогоор k оюутнуудад тэгш хуваарилах явдал юм. Хайрцагнууд нь 1-ээс n хүртэлх тоонуудаас бүрдэх эгнээнд байна гэж бид үзэж болно. даалгавар бол k оюутанд хамгийн олон тооны шоколад тарааж болох хайрцгуудыг сонгох явдал юм. Өгөгдсөн хайрцгуудыг массив гэж үзэж болох бөгөөд arr [i] нь доторх шоколадны тоог i'th индексийн байрлалд илэрхийлж болно.

Жишээ нь

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 оюутнуудад тэгш хуваарилах даалгавар өгсөн. Хайрцаг нь үндсэндээ шоколадны тоог илэрхийлсэн массив юм. Нэг нөхцөл бас бий, бид шоколадыг хуваарилахын тулд дараалсан хайрцгуудыг сонгох ёстой бөгөөд тараалтыг хамгийн дээд хэмжээнд байлгах хэрэгтэй.

Бид ашиглах гэж байна хэшээл. Бид мэдэгдэх болно газрын зураг. Гэхдээ үүнээс өмнө бид өгөгдсөн массивтай ижил хэмжээтэй хоосон массив үүсгэх бөгөөд энэ нь n юм. Нийлбэр [0] -ийг arr [0] -ээр тохируулж, [0] нийлбэрийн эхний утга arr [0] -тай ижил байх ёстой гэсэн үг юм. Дайрч байхдаа массив, бид arr [i] ба sum [i-1] -г нэмж, утгыг sum [i] -д хадгална, ингэснээр массив болон нийлбэрийн өмнөх индекс элементийн утгыг нэмэх болно. Бид түүний нийлбэр массивын утгыг агуулна.

Үүний жишээг авч үзье.

Жишээ нь

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

нийлбэр [0] = arr [0] = 1.

нийлбэр [1] = arr [i] + нийлбэр [i-1] = 6,

нийлбэр [2] = arr [i] + sum [i-1] = 9, үргэлжлүүлбэл бид нийлбэр массивад дараах утгатай байх болно.

нийлбэр [] = {1, 6, 9, 15, 25, 26}.

Бид массивыг дайран өнгөрч, temp sum [i]% k гэж авна. Темп нь 0-тэй тэнцүү байгаа эсэхийг шалгах боловч энэ нь тийм биш тул газрын зураг дээр энэ утгыг агуулаагүй байгаа эсэхийг газрын зураг дээр байгаа индексийн хамт оруулах болно. Тиймээс газрын зураг дээр бид одоо (1,0) байна.

Дараагийн 6 дугаарыг авч, нийлбэр [i]% k-ийг түр зуур шалгах нь 0 болсон нь тогтоогдсон тул үр дүнг одоо шинэчлэх болно. Үр дүн нь 6 байх болно.

Дараагийн элемент нь 9 ба 15 байх бөгөөд энэ хэв маягт хоёулаа 3 модуль нь 0 байх тул 15 хүртэл, үр дүн нь 15 байх болно. Дараагийн тоо нь 25, бид одоо 1-тэй адил температуртай байна. Тиймээс бид үсрэх болно өөр нөхцөл рүү. Гэхдээ бид газрын зураг дээр аль хэдийн 1 оруулсан байна. Тиймээс бид газрын зураг дээр 0 ба 1-ийг хадгалснаар 0-ийн утгыг авах болно. Дараа нь бид [i] -sum [0] нийлбэрийг олж мэдэх бөгөөд энэ нь 24 байх бөгөөд энэ тоог шинэчилнэ үү.

Өөр нэг дугаараар зочилсны дараа бид 24 гэсэн хариулттай хэвээр байна. Эцэст нь 24/3/8 буцаж ирнэ. Энэ бол бидний эцсийн хариулт байх болно.

К оюутнуудад ижил хэмжээгээр тараах шоколадны дээд хэмжээ

Хэрэгжүүлэх

К оюутнуудад ижил хэмжээгээр тараагдах хамгийн их тооны шоколадны C ++ програм

#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) хаана "N" массив дахь элементүүдийн тоо юм.

Сансрын нарийн төвөгтэй байдал

O (N) хаана "N" массив дахь элементүүдийн тоо юм.

лавлагаа