{"id":1513,"date":"2020-07-01T09:32:12","date_gmt":"2020-07-01T09:32:12","guid":{"rendered":"https:\/\/blog.prepbytes.com\/?p=1513"},"modified":"2022-03-21T11:22:30","modified_gmt":"2022-03-21T11:22:30","slug":"fair-distribution-of-chocolates","status":"publish","type":"post","link":"https:\/\/prepbytes.com\/blog\/fair-distribution-of-chocolates\/","title":{"rendered":"Fair Distribution of Chocolates"},"content":{"rendered":"

\"\"<\/p>\n

CONCEPTS USED:<\/h3>\n
\n

Binary Search<\/p>\n<\/blockquote>\n

DIFFICULTY LEVEL:<\/h3>\n
\n

Hard<\/p>\n<\/blockquote>\n

PROBLEM STATEMENT(<\/code>SIMPLIFIED)<\/code>:<\/h3>\n
\n

Given number of chocolates in N<\/code> different bags and M<\/code> children. Every kid will get some consecutive bags. The task is to distribute chocolates in such a way that the maximum number of chocolates assigned to a kid is minimum<\/code>.<\/p>\n<\/blockquote>\n

<\/strong><\/u><\/a><\/p>\n

EXAMPLE<\/strong> :<\/p>\n

Input : chocolates[] = {12, 34, 67, 90}\n        M = 2\n\nOutput : 113\n\nExplanation:\n\nThere are 2 kids. Chocolates can be distributed in following fashion :\n\n  1) [12] and [34, 67, 90]\n      Max number of chocolates is allocated to kid \n      2 with 34 + 67 + 90 = 191 chocolates\n\n  2) [12, 34] and [67, 90]\n      Max number of chocolates is allocated to kid\n      2 with 67 + 90 = 157 chocolates \n\n  3) [12, 34, 67] and [90]\n      Max number of chocolates is allocated to student \n      1 with 12 + 34 + 67 = 113 chocolates\n\nOf the 3 cases, Option 3 has the minimum chocolates = 113. <\/code><\/pre>\n
SOLVING APPROACH:<\/h3>\n
\n
    \n
  1. \n
    The idea is to use Binary Search<\/code>.  <\/p>\n<\/li>\n
  2. \n
    We initialize minimum<\/code> and maximum<\/code> as 0<\/code> and sum-of-all-chocolates<\/code> respectively.<\/p>\n<\/li>\n
  3. \n
    We fix a value for the number of chocolates as mid<\/code> of current minimum<\/code> and maximum<\/code>.<\/p>\n<\/li>\n
  4. \n
    If a current mid<\/code> can be a feasible solution, then we search on the lower half, else we search in higher half.<\/p>\n<\/li>\n
  5. \n
    Before that we need to check if mid<\/code> value is feasible or not. <\/p>\n<\/li>\n
  6. \n
    Basically, we need to check if we can distribute chocolates to all children in a way that the maximum number doesn\u2019t exceed current value. To do this, we sequentially assign chocolates to every kid while the current number of assigned chocolates doesn\u2019t exceed the value.<\/p>\n<\/li>\n
  7. \n
    In this process, if the number of kids becomes more than M<\/code>, then the solution is not feasible. Else feasible.<\/p>\n<\/li>\n<\/ol>\n<\/blockquote>\n
    SOLUTIONS:<\/h3>\n
    \t\t\t\t\t\t