Given counts of x, y, and z, the task is to find the maximum number of triplets that can be made from the count of x, y, and z such that one triplet contains at least one x and at least one y. It is not necessary to use all x, y, and z.
Examples:
Input: countX = 2, countY = 1, countZ = 3
Output: 1
Explanation: The first triplet contains one x, one y, and one z.Input: countX = 3, countY = 4, countZ = 1
Output: 2
Explanation: The first triplet contains one x, one y, and one z.
The second triplet contains two x and one y.
Approach: To solve the problem follow the below idea:
We can solve this problem using binary search because the range from 0 to min(CountX, CountY) is monotonic increasing. Because our answer lies in this range and can’t be greater than min(CountX, CountY) .
Illustration:
Let take example 2: countX = 3, countY = 4, countZ = 1
- Min(countX, CountY) = 3. So our search range will be from 0 to 3.
- First, L = 0 and R = 3, mid = 1; we can find that we can make 1 triplet using one x, one y, and one z.so we will move L to mid + 1. Then update our answer to 1.
- Now, L = 2 and R = 3, mid = 2; we can find that we can make 2 triplets using three x, two y, and one z.so we will move L to mid + 1. Then update our answer to 2.
- Now, L = 3 and R = 3, mid = 3; we see that it is not possible to make 3 triplets using 3 counts of x, 4 counts of y, and 1 count of z . so we will move R to mid -1. Then don’t update our answer because the condition is not satisfy.
- Now, L = 3 and R = 2, Since, L > R, our binary search is complete, and the largest possible answer is 2.
Steps were to follow this problem:
- We will apply a binary search whose range is from 0 to min(countX, countY).
- Then Each time find the middle element of the search space.
- If the middle element satisfies a condition we can make a middle number of triplets such that one triplet contains at least one x and at least one y. Then we will update our search range from mid+1 to r ( where r is the last index of the previous search range) and update our answer to mid.
- If the middle element isn’t satisfied a condition that we can’t make a middle number of triplets such that one triplet contains at least one x and at least one y. Then we will update our search range from l to mid-1 ( where l is the firstindex of the previous search range).
- When the binary search is complete, return the answer ( last mid which is satisfying the condition).
Below is the implementation for the above approach:
C++
// C++ implementation of the above approach#include <bits/stdc++.h>using namespace std;// Function to find maximum number of// triplet that we can make using given// count of x, y and zint maxTriplets(int x, int y, int z){ int l = 0; // Initialize first index of search // range to 0 int r = min(x, y); // Initialize last index of search // range to min(x, y) int ans = 0; while (l <= r) { int mid = (l + r) / 2; // Finding mid of search range bool triplet = false; // Initially assume, we can not // make mid number of triplets if (x >= mid and y >= mid) // Checking if count of x and y is // atleast mid { int remx = x - mid; // x remaining after x mid // fixed in mid triplet int remy = y - mid; // y remaining after y mid // fixed in mid triplet // Adding extra count x and // y and count of z int remaining = remx + remy + z; if (remaining >= mid) // Checking we can make // mid no. of triplet { triplet = true; } } // Checking if we can make mid // number of triplet or not if (triplet) { // If we can make mid number // of triplet ans = mid; // Update our answer l = mid + 1; // Update search range to // [mid+1, R] because we can make // atleast mid no. of triplets } else { r = mid - 1; // If we can't make mid number // of triplet update search range // to [l, mid-1] because we can // not make mid no. of triplets } } return ans; // Return answer}// Drive Codeint main(){ int x = 2, y = 1, z = 3; // Function call for test case 1 cout << maxTriplets(x, y, z) << "\n"; x = 3, y = 4, z = 1; // Function call for test case 2 cout << maxTriplets(x, y, z) << "\n"; return 0;} |
Java
import java.util.*;public class Main { // Function to find maximum number of // triplet that we can make using given // count of x, y and z public static int maxTriplets(int x, int y, int z) { int l = 0; // Initialize first index of search // range to 0 int r = Math.min(x, y); // Initialize last index of search // range to min(x, y) int ans = 0; while (l <= r) { int mid = (l + r) / 2; // Finding mid of search range boolean triplet = false; // Initially assume, we can not // make mid number of triplets if (x >= mid && y >= mid) // Checking if count of x and y is // atleast mid { int remx = x - mid; // x remaining after x mid // fixed in mid triplet int remy = y - mid; // y remaining after y mid // fixed in mid triplet // Adding extra count x and // y and count of z int remaining = remx + remy + z; if (remaining >= mid) // Checking we can make // mid no. of triplet { triplet = true; } } // Checking if we can make mid // number of triplet or not if (triplet) { // If we can make mid number // of triplet ans = mid; // Update our answer l = mid + 1; // Update search range to // [mid+1, R] because we can make // atleast mid no. of triplets } else { r = mid - 1; // If we can't make mid number // of triplet update search range // to [l, mid-1] because we can // not make mid no. of triplets } } return ans; // Return answer } // Driver Code public static void main(String[] args) { int x = 2, y = 1, z = 3; // Function call for test case 1 System.out.println(maxTriplets(x, y, z)); x = 3; y = 4; z = 1; // Function call for test case 2 System.out.println(maxTriplets(x, y, z)); }} |
C#
// C# implementation of the above approachusing System;public class GFG { // Function to find maximum number of triplet that we // can make using given count of x, y and z public static int maxTriplets(int x, int y, int z) { int l = 0; // Initialize first index of search range to 0 int r = Math.Min(x, y); // Initialize last index of search range to min(x, y) int ans = 0; while (l <= r) { int mid = (l + r) / 2; // Finding mid of search range bool triplet = false; // Initially assume, we can not make mid number // of triplets if (x >= mid && y >= mid) // Checking if count of x and y is atleast mid { int remx = x - mid; // x remaining after x mid fixed in mid // triplet int remy = y - mid; // y remaining after y mid fixed in mid // triplet // Adding extra count x and y and count of z int remaining = remx + remy + z; if (remaining >= mid) // Checking we can make mid no. of triplet { triplet = true; } } // Checking if we can make mid number of triplet // or not if (triplet) { // If we can make mid number of triplet ans = mid; // Update our answer l = mid + 1; // Update search range to [mid+1, R] because // we can make atleast mid no. of triplets } else { r = mid - 1; // If we can't make mid number of triplet // update search range to [l, mid-1] because // we can not make mid no. of triplets } } return ans; // Return answer } static public void Main() { // Code int x = 2, y = 1, z = 3; // Function call for test case 1 Console.WriteLine(maxTriplets(x, y, z)); x = 3; y = 4; z = 1; // Function call for test case 2 Console.WriteLine(maxTriplets(x, y, z)); }}// This code is contribtuted by sankar. |
Python3
# Python3 implementation of the above approachprint("GFG")# Function to find maximum number of# triplet that we can make using given# count of x, y and zdef maxTriplets(x: int, y: int, z: int) -> int: # Initialize first index of search range to 0 l = 0 # Initialize last index of search range to min(x, y) r = min(x, y) # Initialize answer to 0 ans = 0 # Binary search loop while l <= r: # Finding mid of search range mid = (l + r) // 2 # Initially assume, we can not make mid number of triplets triplet = False # Checking if count of x and y is atleast mid if x >= mid and y >= mid: # x remaining after x mid fixed in mid triplet remx = x - mid # y remaining after y mid fixed in mid triplet remy = y - mid # Adding extra count x and y and count of z remaining = remx + remy + z # Checking we can make mid no. of triplet if remaining >= mid: triplet = True # Checking if we can make mid number of triplet or not if triplet: # If we can make mid number of triplet ans = mid # Update search range to [mid+1, R] because we can make # atleast mid no. of triplets l = mid + 1 else: # If we can't make mid number of triplet update search range # to [l, mid-1] because we can not make mid no. of triplets r = mid - 1 # Return the answer return ans# Driver Codeif __name__ == '__main__': x = 2 y = 1 z = 3 # Function call for test case 1 print(maxTriplets(x, y, z)) x = 3 y = 4 z = 1 # Function call for test case 2 print(maxTriplets(x, y, z)) |
Javascript
// JavaScript implementation of the above approachprint("GFG")// Function to find maximum number of// triplet that we can make using given// count of x, y and zfunction maxTriplets(x, y, z) { let l = 0; // Initialize first index of search // range to 0 let r = Math.min(x, y); // Initialize last index of search // range to min(x, y) let ans = 0; while (l <= r) { let mid = Math.floor((l + r) / 2); // Finding mid of search range let triplet = false; // Initially assume, we can not // make mid number of triplets if (x >= mid && y >= mid) // Checking if count of x and y is // at least mid { let remx = x - mid; // x remaining after x mid // fixed in mid triplet let remy = y - mid; // y remaining after y mid // fixed in mid triplet // Adding extra count x and // y and count of z let remaining = remx + remy + z; if (remaining >= mid) // Checking we can make // mid no. of triplet { triplet = true; } } // Checking if we can make mid // number of triplet or not if (triplet) { // If we can make mid number // of triplet ans = mid; // Update our answer l = mid + 1; // Update search range to // [mid+1, R] because we can make // at least mid no. of triplets } else { r = mid - 1; // If we can't make mid number // of triplet update search range // to [l, mid-1] because we can // not make mid no. of triplets } } return ans; // Return answer}// Driver Codelet x = 2, y = 1, z = 3;// Function call for test case 1console.log(maxTriplets(x, y, z));x = 3, y = 4, z = 1;// Function call for test case 2console.log(maxTriplets(x, y, z)); |
Output
1 2
Time Complexity: O(log2n)
Auxiliary Space: O(1)
Efficient Approach: We can also solve this problem efficiently by making these observations:
- We can see that the maximum number of triplets can be made that contain at least one x and one y can’t be greater than the minimum count of x and y.
- If the count of z is greater than or equal to the minimum(count of x, count of y). So our answer will be minimum(count of x, count of y) because we have used our all x or y in making ‘a’ number of triplets where an equal to the minimum( count of x, count of y).
- If the count of z is less than the minimum(count of x, count of y), then our answer will be less than the minimum of the count of x and y and the answer will be the sum no. of triplets can be made using the count of x, y and z and no. of triplets that can be made using the count of x and y only such that one triplet contain at least one x and at least one y.
- Finally, return our final answer.
Below is the implementation of the above approach:
C++
// C++ program for the above approach#include <bits/stdc++.h>using namespace std;// Function to find the maximum number of// triplets can be made that contain// least one x and one yint maxTriplets(int x, int y, int z){ int mi = min(x, y), ans; if (mi <= z) // If min(x, y) less than or equal to // count of z // Then triplets can be made at // most min(x, y) { ans = mi; } else // If min(x, y) greater than count of z { ans = z; // Then first we add z to our // answer because we x -= z; // can make atleast count // of z triplet y -= z; // Using all count of z mi = min(x, y); // min(x, y), after making count // of z triplets int ma = max(x, y); // max(x, y), after making count // of z triplets if (mi * 2 <= ma) { // If 2 times of min <= ma, so // we can make at most mi // triplets using count of // x and y only. // In mi*2 <= ma, we can't use // all count of x and y. ans += mi; } else { // Otherwise we can make (mi+ma)/3 // triplet using count of x and y // only because if mi*2>ma we can // make triplet using all x and y ans += (mi + ma) / 3; } } return ans; // Return final answer}// Driver's codeint main(){ int x = 2, y = 1, z = 3; // Function call for test case 1 cout << maxTriplets(x, y, z) << "\n"; x = 3, y = 4, z = 1; // Function call for test case 2 cout << maxTriplets(x, y, z) << "\n"; return 0;} |
Java
// Java program for the above approachimport java.util.*;class GFG { // Function to find the maximum number of triplets can be made that contain // least one x and one y public static int maxTriplets(int x, int y, int z) { int mi = Math.min(x, y), ans; if (mi <= z) // If min(x, y) less than or equal to // count of z // Then triplets can be made at // most min(x, y) ans = mi; else // If min(x, y) greater than count of z { ans = z; // Then first we add z to our // answer because we x -= z; // can make at least count // of z triplet y -= z; // Using all count of z mi = Math.min(x, y); // min(x, y), after making count // of z triplets int ma = Math.max(x, y); // max(x, y), after making count // of z triplets if (mi * 2 <= ma) { // If 2 times of min <= ma, so // we can make at most mi // triplets using count of // x and y only. // In mi*2 <= ma, we can't use // all count of x and y. ans += mi; } else { // Otherwise we can make (mi+ma)/3 // triplet using count of x and y // only because if mi*2>ma we can // make triplet using all x and y ans += (mi + ma) / 3; } } return ans; // Return final answer } // Driver's code public static void main(String[] args) { int x = 2, y = 1, z = 3; // Function call for test case 1 System.out.println(maxTriplets(x, y, z)); x = 3; y = 4; z = 1; // Function call for test case 2 System.out.println(maxTriplets(x, y, z)); }} |
Python3
# Java program for the above approach# Function to find the maximum number of triplets can be made that contain# least one x and one ydef maxTriplets(x, y, z): mi = min(x, y) ans = 0 if mi <= z: # If min(x, y) less than or equal to # count of z # Then triplets can be made at # most min(x, y) ans = mi else: # If min(x, y) greater than count of z ans = z # Then first we add z to our answer # because we can make atleast count of z triplet x -= z y -= z # Using all count of z mi = min(x, y) # min(x, y), after making count of z triplets ma = max(x, y) # max(x, y), after making count of z triplets if mi * 2 <= ma: # If 2 times of min <= ma, so # we can make at most mi # triplets using count of x and y only. # In mi*2 <= ma, we can't use all count of x and y. ans += mi else: # Otherwise we can make (mi+ma)/3 # triplet using count of x and y # only because if mi*2>ma we can # make triplet using all x and y ans += (mi + ma) // 3 return ans# Driver's codex, y, z = 2, 1, 3# Function call for test case 1print(maxTriplets(x, y, z))x, y, z = 3, 4, 1# Function call for test case 2print(maxTriplets(x, y, z)) |
C#
// C# program for the above approachusing System;namespace MaxTriplets{ class GFG { // Function to find the maximum number of triplets // that can be made that contain at least one x and one y static int maxTriplets(int x, int y, int z) { int mi = Math.Min(x, y); int ans; if (mi <= z) { // If min(x, y) is less than or equal to // count of z, then triplets can be made at // most min(x, y) ans = mi; } else { // If min(x, y) is greater than count of z ans = z; // Then first we add z to our answer because we // can make at least count of z triplet x -= z; // Using all count of z y -= z; mi = Math.Min(x, y); // min(x, y), after making count of z triplets int ma = Math.Max(x, y); // max(x, y), after making count of z triplets if (mi * 2 <= ma) { // If 2 times of min <= ma, so we can make at most mi // triplets using count of x and y only. // In mi*2 <= ma, we can't use all count of x and y. ans += mi; } else { // Otherwise we can make (mi+ma)/3 triplet using count of x and y // only because if mi*2>ma we can make triplet using all x and y ans += (mi + ma) / 3; } } return ans; } // Driver code static void Main(string[] args) { int x = 2, y = 1, z = 3; // Function call for test case 1 Console.WriteLine(maxTriplets(x, y, z)); x = 3; y = 4; z = 1; // Function call for test case 2 Console.WriteLine(maxTriplets(x, y, z)); } }} |
Javascript
// Javascript program for the above approach// Function to find the maximum number of// triplets can be made that contain// least one x and one yfunction maxTriplets(x, y, z){ let mi = Math.min(x, y), ans; if (mi <= z) { // If min(x, y) less than or equal to // count of z // Then triplets can be made at // most min(x, y) ans = mi; } else { // If min(x, y) greater than count of z ans = z; // Then first we add z to our answer // because we can make atleast count // of z triplet x -= z; y -= z; // Using all count of z mi = Math.min(x, y); // min(x, y), after making count // of z triplets let ma = Math.max(x, y); // max(x, y), after making count // of z triplets if (mi * 2 <= ma) { // If 2 times of min <= ma, so // we can make at most mi // triplets using count of // x and y only. // In mi*2 <= ma, we can't use // all count of x and y. ans += mi; } else { // Otherwise we can make (mi+ma)/3 // triplet using count of x and y // only because if mi*2>ma we can // make triplet using all x and y ans += Math.floor((mi + ma) / 3); } } return ans; // Return final answer}// Driver's codelet x = 2, y = 1, z = 3;// Function call for test case 1console.log(maxTriplets(x, y, z));x = 3, y = 4, z = 1;// Function call for test case 2console.log(maxTriplets(x, y, z)); |
Output
1 2
Time Complexity: O(1)
Auxiliary Space: O(1)
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Share your thoughts in the comments
