Minimum number of bottles required to fill K glasses
Given N glasses having water, and a list A 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.
Examples:
Input: N = 4, K = 3, arr[] = {200, 150, 140, 300} Output: 5 We have to fill out exactly 3 glasses. So we fill out 140, 150, 200 whose sum is 490, so we need 5 bottles for this.
Input: N = 5, K = 4, arr[] = {1, 2, 3, 2, 1} Output: 1
Approach: To fill out exactly K glasses, take the K glasses with the least capacity. So for this sort the list of given capacities. The final answer will be the ceiling value of (Sum of capacities of 1st k glasses) / (Capacity of 1 bottle).
Below is the implementation of the above approach:
C++
// C++ implementation of the approach #include <bits/stdc++.h> using namespace std; // function to calculate minimum glasses double Min_glass( int n, int k, int a[]) { // sort the array based on // their capacity int sum = 0; // taking sum of capacity // of first k glasses for ( int i = 0; i < k; i++) sum += a[i]; // calculate the answer double ans = ceil (( double )sum / ( double )100); return ans; } // Driver code int main() { int n = 4; int k = 3; int a[] = { 200, 150, 140, 300 }; sort(a, a+n); cout << Min_glass(n, k, a); return 0; } // This code is contributed by target_2. |
C
// C implementation of the approach #include <stdio.h> #include<math.h> // function to calculate minimum glasses double Min_glass( int n, int k, int a[]) { // sort the array based on // their capacity int sum = 0; // taking sum of capacity // of first k glasses for ( int i = 0; i < k; i++) sum += a[i]; // calculate the answer double ans = ceil (( double )sum / ( double )100); return ans; } // Driver code int main() { int n = 4; int k = 3; int temp=0; int a[] = { 200, 150, 140, 300 }; int length = sizeof (a)/ sizeof (a[0]); // swapping the array in ascending order for ( int i = 0; i < length; i++) { for ( int j = i+1; j < length; j++) { if (a[i] > a[j]) { temp = a[i]; a[i] = a[j]; a[j] = temp; } } } printf ( "%.0f" ,Min_glass(n, k, a)); return 0; } // This code is contributed by allwink45. |
Java
// Java implementation of the // above approach import java.util.*; class GFG { // function to calculate minimum glasses public static double Min_glass( int n, int k, int [] a) { // sort the array based on // their capacity int sum = 0 ; // taking sum of capacity // of first k glasses for ( int i = 0 ; i < k; i++) sum += a[i]; // calculate the answer double ans = Math.ceil(( double )sum / ( double ) 100 ); return ans; } // Driver code public static void main(String[] args) { int n = 4 ; int k = 3 ; int [] a = { 200 , 150 , 140 , 300 }; Arrays.sort(a); System.out.println(Min_glass(n, k, a)); } } // This code is contributed by mits |
Python3
# Python3 implementation of the above approach from math import ceil # Function to calculate minimum glasses def Min_glass(n, k, a): # sort the array based on their capacity a.sort() # calculate the answer return ceil( sum (a[:k]) / 100 ) # Driver code if __name__ = = "__main__" : n, k = 4 , 3 a = [ 200 , 150 , 140 , 300 ] print (Min_glass(n, k, a)) # This code is contributed by Rituraj Jain |
C#
// C# implementation of the // above approach using System; class GFG { // function to calculate minimum glasses public static double Min_glass( int n, int k, int []a) { // sort the array based on // their capacity int sum = 0; // taking sum of capacity // of first k glasses for ( int i = 0; i < k; i++) sum += a[i]; // calculate the answer double ans = Math.Ceiling(( double )sum / ( double )100); return ans; } // Driver code public static void Main() { int n = 4; int k = 3; int [] a = { 200, 150, 140, 300 }; Array.Sort(a); Console.WriteLine(Min_glass(n, k, a)); } } // This code is contributed // by Soumik Mondal |
PHP
<?php // PHP implementation of the above approach // function to calculate minimum glasses function Min_glass( $n , $k , $a ) { // sort the array based on // their capacity sort( $a ); $sum = 0; // taking sum of capacity // of first k glasses for ( $i = 0; $i < $k ; $i ++) $sum += $a [ $i ]; // calculate the answer $ans = ceil ( $sum /100); return $ans ; } // Driver code $n = 4; $k = 3; $a = array ( 200, 150, 140, 300 ); echo Min_glass( $n , $k , $a ); // This code is contributed // by akt_mit ?> |
Javascript
<script> // Javascript implementation of the // above approach // Function to calculate minimum glasses function Min_glass(n, k, a) { // Sort the array based on // their capacity var sum = 0; // Taking sum of capacity // of first k glasses for ( var i = 0; i < k; i++) sum += a[i]; // Calculate the answer var ans = parseInt(Math.ceil(sum / 100)); return ans; } // Driver Code var n = 4; var k = 3; var a = [ 200, 150, 140, 300 ]; a.sort(); document.write(Min_glass(n, k, a)); // This code is contributed by Ankita saini </script> |
Output:
5
Time Complexity: O(nlog(n)), since best sorting algorithm takes nlog(n) times.
Auxiliary Space: O(1), since no extra space has been taken.
Contact Us