Maximizing Vessels with Unique Element Sizes
Given an array of elements[] of size N where elements[i] represent that we can use element i for at most elements[i] number of times, the task is to form the maximum number of vessels with elements, such that each vessel must have distinct elements (no vessel should have duplicate elements) and the size of each vessel must be different.
Examples:
Input: elements[] = {3, 1, 5}, N = 3
Output: 3
Explanation: We can use 0 at most 3 times, 1 at most twice, and 2 at most 5 times:
- Vessel 1: [2]
- Vessel 2: [0, 2]
- Vessel 3: [0, 1, 2]
So, the maximum output is 3 as each Vessel size is different and each Vessel contains unique elements.
Input: element[] = {3, 3, 12, 200}, N = 4
Output: 4
Explanation: We can use 0 at most 3 times, 1 at most 3 times, 2 at most 12 times, and 3 at most 200 times:
- Vessel 1: [3]
- Vessel 2: [3, 2]
- Vessel 3: [3, 2, 1]
- Vessel 2: [3, 2, 1, 0]
So, the maximum output is 4 as each Vessel size is different and each Vessel contains unique elements.
Approach: This can be solved by the following approach:
Firstly, we sort the elements[] array in ascending order by their limit. To form k vessel we need at least 1 + 2 + … + k elements. So, if we are having x elements
- If x < k + 1, we don’t have enough elements, need to wait for more elements to come in.
- If x >= k + 1, we can fill the (k + 1)th Vessel.
But we can not have the (k + 2)th Vessel directly, even we have enough elements. Because in n vessels, we can use one elements at most n times.
Steps to solve the problem:
- Sort the given elements[] array.
- Maintain a variable x to count number of elements present and k be the maximum vessels formed to far.
- In order to fill a new vessel, the (k+1)th vessel, we will need at least (k+1) more elements, which means total available elements should be ((k + 1) * (k + 2)) / 2.
- So at every element i, we add elements[i] to the variable x and see if we have total vessels greater than ((k + 1) * (k + 2)) / 2, then increment the vessel count k by 1.
- At last, print the final answer k.
Below is the implementation of the code:
C++
// C++ code for the above implementation: #include <bits/stdc++.h> using namespace std; // Function to count maximum number of // vessels int maximumVessels(vector< int > elements, int N) { // Sort the elements vector sort(elements.begin(), elements.end()); long long x = 0, k = 0; for ( int a : elements) { x += a; if (x >= ((k + 1) * (k + 2)) / 2) k++; } // Return the maximum vessels return k; } // Driver code int main() { int N = 4; vector< int > elements = { 3, 3, 12, 200 }; // Function call int res = maximumVessels(elements, N); cout << res << endl; return 0; } |
Java
// JAVA code for the above implementation: import java.util.Arrays; class GFG { // Function to calculate the maximum number of vessels public static int maximumVessels( int [] elements) { Arrays.sort(elements); int x = 0 ; // Initialize the cumulative sum int k = 0 ; // Initialize the number of vessels for ( int a : elements) { x += a; if (x >= (k + 1 ) * (k + 2 ) / 2 ) { k++; // Increment the number of vessels } } return k; // Return the maximum number of vessels } public static void main(String[] args) { int N = 4 ; int [] elements = { 3 , 3 , 12 , 200 }; int res = maximumVessels(elements); System.out.println(res); // Print the result } } // This code is contributed by Taranpreet Singh. |
Python3
def maximum_vessels(elements): elements.sort() x = 0 k = 0 for a in elements: x + = a if x > = (k + 1 ) * (k + 2 ) / / 2 : k + = 1 return k # Driver code N = 4 elements = [ 3 , 3 , 12 , 200 ] # Function call res = maximum_vessels(elements) print (res) |
C#
using System; using System.Collections.Generic; using System.Linq; class Program { // Function to count the maximum number of vessels static int MaximumVessels(List< int > elements, int N) { // Sort the elements list elements.Sort(); long x = 0, k = 0; foreach ( int a in elements) { x += a; if (x >= ((k + 1) * (k + 2)) / 2) k++; } // Return the maximum vessels return ( int )k; } static void Main() { int N = 4; List< int > elements = new List< int > { 3, 3, 12, 200 }; // Function call int res = MaximumVessels(elements, N); Console.WriteLine(res); } } |
Javascript
function GFG(elements) { elements.sort((a, b) => a - b); let x = 0; // Initialize the cumulative sum let k = 0; // Initialize the number of vessels for (const a of elements) { x += a; if (x >= (k + 1) * (k + 2) / 2) { k++; // Increment the number of vessels } } return k; // Return the maximum number of vessels } // Driver Code const N = 4; const elements = [3, 3, 12, 200]; const res = GFG(elements); console.log(res); // Print the result |
4
Time Complexity: O(N), where N is the size of the elements[] array.
Auxiliary space: O(1)
Contact Us