จำนวนช็อคโกแลตสูงสุดที่จะแจกจ่ายในหมู่นักเรียน k เท่า ๆ กัน  


ระดับความยาก กลาง
ถามบ่อยใน แอคเซนเจอร์ อะโดบี อเมซอน Facebook โฟร์ไคต์
แถว กัญชา

“ จำนวนช็อคโกแลตสูงสุดที่จะแจกจ่ายในหมู่นักเรียน k เท่า ๆ กัน” ระบุว่าคุณจะได้รับ n กล่องที่มีช็อคโกแลตอยู่ในนั้น สมมติว่ามีนักเรียน k ภารกิจคือแจกจ่ายช็อคโกแลตจำนวนสูงสุดให้กับนักเรียน k เท่า ๆ กันโดยเลือกกล่องที่ต่อเนื่องกัน เราสามารถสันนิษฐานได้ว่ากล่องอยู่ในแถวที่ประกอบด้วยตัวเลขตั้งแต่ 1 ถึง n ภารกิจคือการเลือกกลุ่มกล่องที่สามารถแจกจ่ายช็อคโกแลตจำนวนมากที่สุดให้กับนักเรียน k เท่า ๆ กัน กล่องที่กำหนดให้ถือได้ว่าเป็นอาร์เรย์และ arr [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 อย่างเท่าเทียมกัน กล่องนี้เป็นอาร์เรย์ที่แสดงถึงจำนวนช็อคโกแลต นอกจากนี้ยังมีเงื่อนไขประการหนึ่งคือเราต้องเลือกกล่องที่ต่อเนื่องกันเพื่อกระจายช็อคโกแลตและการกระจายควรขยายให้ใหญ่ที่สุด

ดูสิ่งนี้ด้วย
การออกแบบโครงสร้างข้อมูล

เรากำลังจะใช้ hashing. เราจะประกาศก แผนที่. แต่ก่อนหน้านั้นเราจะสร้างอาร์เรย์ว่างที่มีขนาดเท่ากับอาร์เรย์ที่กำหนดนั่นคือ n กำหนดค่า sum [0] เป็นของ arr [0] หมายถึงค่าแรกของ sum [0] ควรจะเหมือนกับ arr [0] ในขณะที่ข้าม แถวเราจะเพิ่ม arr [i] และ sum [i-1] และเก็บค่าเป็น sum [i] ในลักษณะนี้เราจะเพิ่มค่าของอาร์เรย์และองค์ประกอบดัชนีก่อนหน้าของ sum เราจะมีค่าในมันรวมอาร์เรย์

ให้เรายกตัวอย่าง:

ตัวอย่าง

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

ผลรวม [0] = arr [0] = 1

ผลรวม [1] = arr [i] + ผลรวม [i-1] = 6,

sum [2] = arr [i] + sum [i-1] = 9 ต่อไปเราจะมีค่าต่อไปนี้ใน sum array

ผลรวม [] = {1, 6, 9, 15, 25, 26}

เราจะสำรวจอาร์เรย์อีกครั้งโดยรับ temp เป็น sum [i]% k เราจะตรวจสอบว่าอุณหภูมิเท่ากับ 0 หรือไม่ แต่ไม่ใช่ดังนั้นเราจะตรวจสอบว่าแผนที่ไม่มีค่านี้หรือไม่เราจะวางไว้พร้อมกับดัชนีปัจจุบันในแผนที่ บนแผนที่ตอนนี้เรามี (1,0)

เมื่อเลือกหมายเลข 6 ถัดไปและตรวจสอบ sum [i]% k เป็น temp จะพบว่าตอนนี้เป็น 0 ดังนั้นเราจะอัปเดตผลลัพธ์ทันที ผลลัพธ์จะเป็น 6

องค์ประกอบถัดไปจะเป็น 9 และ 15 ในรูปแบบนี้ทั้งคู่มีโมดูโลถึง 3 เป็น 0 ดังนั้นมากถึง 15 ผลลัพธ์จะเป็น 15 ตัวเลขถัดไปคือ 25 เรามี temp ตอนนี้เหมือน 1 ดังนั้นเราจะข้ามไปที่ เป็นเงื่อนไขอื่น แต่เรามี 1 อยู่แล้วในแผนที่ เราจะได้ค่าของมันและนั่นคือ 0 เมื่อเราเก็บ 1 และ 0 ไว้ในแผนที่ จากนั้นเราจะหาผลรวม [i] -sum [0] และนั่นคือ 24 อัปเดตผลลัพธ์เป็นตัวเลขนี้

ดูสิ่งนี้ด้วย
ค้นหาลำดับต่อมาของขนาด 3 ในเวลาเชิงเส้น

หลังจากเยี่ยมชมอีกหนึ่งหมายเลขเรายังคงมีคำตอบเหมือน 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 สำหรับจำนวนช็อคโกแลตสูงสุดที่จะแจกจ่ายอย่างเท่าเทียมกันในหมู่นักเรียน 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 อย่างเท่าเทียมกัน  

ความซับซ้อนของเวลา

O (n) ที่ไหน “ n” คือจำนวนองค์ประกอบในอาร์เรย์

ดูสิ่งนี้ด้วย
จำนวนคู่ที่เทียบเท่ากับโซลูชัน Leetcode ของ Domino

ความซับซ้อนของอวกาศ

O (n) ที่ไหน “ n” คือจำนวนองค์ประกอบในอาร์เรย์

อ้างอิง