Get free ebooK with 50 must do coding Question for Product Based Companies solved
Fill the details & get ebook over email
Thank You!
We have sent the Ebook on 50 Must Do Coding Questions for Product Based Companies Solved over your email. All the best!

Fair Distribution of Chocolates

Last Updated on March 21, 2022 by Ria Pathak

CONCEPTS USED:

Binary Search

DIFFICULTY LEVEL:

Hard

PROBLEM STATEMENT(SIMPLIFIED):

Given number of chocolates in N different bags and M 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.

See original problem statement here

EXAMPLE :

Input : chocolates[] = {12, 34, 67, 90}
        M = 2

Output : 113

Explanation:

There are 2 kids. Chocolates can be distributed in following fashion :

  1) [12] and [34, 67, 90]
      Max number of chocolates is allocated to kid 
      2 with 34 + 67 + 90 = 191 chocolates

  2) [12, 34] and [67, 90]
      Max number of chocolates is allocated to kid
      2 with 67 + 90 = 157 chocolates 

  3) [12, 34, 67] and [90]
      Max number of chocolates is allocated to student 
      1 with 12 + 34 + 67 = 113 chocolates

Of the 3 cases, Option 3 has the minimum chocolates = 113. 

SOLVING APPROACH:

  1. The idea is to use Binary Search.

  2. We initialize minimum and maximum as 0 and sum-of-all-chocolates respectively.

  3. We fix a value for the number of chocolates as mid of current minimum and maximum.

  4. If a current mid can be a feasible solution, then we search on the lower half, else we search in higher half.

  5. Before that we need to check if mid value is feasible or not.

  6. Basically, we need to check if we can distribute chocolates to all children in a way that the maximum number doesn’t exceed current value. To do this, we sequentially assign chocolates to every kid while the current number of assigned chocolates doesn’t exceed the value.

  7. In this process, if the number of kids becomes more than M, then the solution is not feasible. Else feasible.

SOLUTIONS:


#include <stdio.h>
#include <limits.h>

//function for finding if assumed minimum is possible or not
int isPossible(int *arr, int n, int m, long long curr_min){

  long long  curr_sum = 0;
  int studentRequired = 1;
  for(int i=0; i<n; i++){
    /* if any value in array is greater than current minimum
      value then it is not a valid value and therefore return */
    if(arr[i] > curr_min)
      return 0;

    if(arr[i] + curr_sum > curr_min){

      studentRequired++;
      curr_sum = arr[i];
      /* if at any point required student becomes greater
          than actual student return false */
      if(studentRequired > m)
        return 0;
    }
    else{
      curr_sum += arr[i];
    }
  }
  return 1;
}

long long solution(int *arr, int n, int m){

  long long  sum = 0;
  //finding sum of all elements
  for(int i=0 ;i<n; i++)
    sum += arr[i];

  //if books are less than students
  if(n < m)
    return -1;

  //assume minimum pages to be start and maximum pages to be end
  int start = 0;
  int end = sum;

  long long result = LLONG_MAX;

  while(start <= end){
    //we assume that this mid value can be our minimum pages
    long long mid = start + (end - start) / 2;

    /* if mid value is possible, store it and 
    go on searching for a lower value of mid */
    if(isPossible(arr, n, m, mid)){

      if(mid < result)
        result = mid;
      end = mid - 1;
    }
    /* if not possible search in the right half
      for a possible value */
    else{
      start = mid + 1;
    }
  }
  return result;
}

int main()
{
  int t; scanf("%d", &t);
  while(t--){
    int n, k; scanf("%d", &n);
    int arr[n];
    for(int i=0; i<n; i++){
      scanf("%d", &arr[i]);
    }
    scanf("%d", &k);

    printf("%lld\n", solution(arr, n, k));
  }
  return 0;
}

#include <bits/stdc++.h>
using namespace std;

//function for finding if assumed minimum is possible or not
int isPossible(int *arr, int n, int m, long long curr_min){

  long long  curr_sum = 0;
  int studentRequired = 1;
  for(int i=0; i<n; i++){
    /* if any value in array is greater than current minimum
      value then it is not a valid value and therefore return */
    if(arr[i] > curr_min)
      return 0;

    if(arr[i] + curr_sum > curr_min){

      studentRequired++;
      curr_sum = arr[i];
      /* if at any point required student becomes greater
          than actual student return false */
      if(studentRequired > m)
        return 0;
    }
    else{
      curr_sum += arr[i];
    }
  }
  return 1;
}

int solution(int *arr, int n, int m){

  long long  sum = 0;
  //finding sum of all elements
  for(int i=0 ;i<n; i++)
    sum += arr[i];

  //if books are less than students
  if(n < m)
    return -1;

  //assume minimum pages to be start and maximum pages to be end
  int start = 0;
  int end = sum;

  long long result = INT_MAX;

  while(start <= end){
    //we assume that this mid value can be our minimum pages
    long long mid = start + (end - start) / 2;

    /* if mid value is possible, store it and 
    go on searching for a lower value of mid */
    if(isPossible(arr, n, m, mid)){

      result = min(result, mid);
      end = mid - 1;
    }
    /* if not possible search in the right half
      for a possible value */
    else{
      start = mid + 1;
    }
  }
  return result;
}

int main()
{
  int t; cin>>t;
  while(t--){
    int n, k; cin>>n;
    int arr[n];
    for(int i=0; i<n; i++){
      cin>>arr[i];
    }
    cin>>k;

    cout<<solution(arr, n, k)<<"\n";
  }
  return 0;
}

import java.util.*;
import java.io.*;

public class Main {

  //function for finding if assumed minimum is possible or not
  static boolean isPossible(int []arr, int n, int m, long curr_min){

    long curr_sum = 0;
    int studentRequired = 1;
    for(int i=0; i<n; i++){
      /* if any value in array is greater than current minimum
        value then it is not a valid value and therefore return */
      if(arr[i] > curr_min)
        return false;

      if(arr[i] + curr_sum > curr_min){

        studentRequired++;
        curr_sum = arr[i];
        /* if at any point required student becomes greater
            than actual student return false */
        if(studentRequired > m)
          return false;
      }
      else{
        curr_sum += arr[i];
      }
    }
    return true;
  }

  static long solution(int []arr, int n, int m){

    long  sum = 0;
    //finding sum of all elements
    for(int i=0 ;i<n; i++)
      sum += arr[i];

    //if books are less than students
    if(n < m)
      return -1;

    //assume minimum pages to be start and maximum pages to be end
    long start = 0;
    long end = sum;

    long result = Long.MAX_VALUE;

    while(start <= end){
      //we assume that this mid value can be our minimum pages
      long mid = start + (end - start) / 2;

      /* if mid value is possible, store it and 
      go on searching for a lower value of mid */
      if(isPossible(arr, n, m, mid)){

        result = Math.min(result, mid);
        end = mid - 1;
      }
      /* if not possible search in the right half
        for a possible value */
      else{
        start = mid + 1;
      }
    }
    return result;
  }

  public static void main(String args[]) throws IOException {

    Scanner sc = new Scanner(System.in);
    int t = sc.nextInt();
    while(t != 0){
      int n  = sc.nextInt();
      int arr[] = new int[n];
      for(int i=0; i<n; i++){
        arr[i] = sc.nextInt();
      }
      int k  = sc.nextInt();
      System.out.println(solution(arr, n, k));
      t--;
    }
  }
}

Space Complexity is O(1)

[forminator_quiz id="1532"]

So, in this blog, we have tried to explain binary search. If you want to solve more questions on Searching, which are curated by our expert mentors at PrepBytes, you can follow this link Searching.

Leave a Reply

Your email address will not be published. Required fields are marked *