Minimum number of bottles required to fill K glasses in C++

Problem statement

Given N glasses having water, and a list of each of their capacity. The task is to find the minimum number of bottles required to fill out exactly K glasses. The capacity of each bottle is 100 units.

Example

If N = 5, K = 4, capacity[] = {1, 2, 3, 2, 1}.

• Filling the glasses with capacities 2, 3, 2, requires 8units.
• This way, it's enough to open just 1 bottle.

Algorithm

• To fill out exactly K glasses, take the K glasses with least capacity

• Total required bottles can be calculated as −

  Ceil value of (Sum of capacities of 1st k glasses) / (Capacity of 1 bottle).

Example

#include <iostream> #include <algorithm> #include <cmath> using namespace std; int minBottles(int *capacity, int n, int k) {    sort(capacity, capacity + n);    int sum = 0;    for (int i = 0; i < k; ++i) {       sum += capacity[i];    }    return ceil((double)sum/100); } int main() {    int capacity[] = {1, 2, 3, 2, 1};    cout << "Min bottles required = " <<minBottles(capacity, 5, 4) << endl;    return 0; }

Output

When you compile and execute above program. It generates following output −

Min bottles required = 1