Fair Distribution of Chocolates

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 according to data structures in c++.

  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)

Previous post Zigzag String
Next post Find Mountain Top

Leave a Reply

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