Maximum triplets containing atleast one x and one y

By Ann Roberts On Feb 20, 2023

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 z
int maxTriplets(int x, int y, int z)
{
    int l = 0;

    // Intialize first index of search
    // range to 0
    int r = min(x, y);

    // Intialize 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 Code
int main()
{
    int x = 2, y = 1, z = 3;

    // Funtion call for test case 1
    cout << maxTriplets(x, y, z) << "\n";

    x = 3, y = 4, z = 1;

    // Funtion call for test case 2
    cout << maxTriplets(x, y, z) << "\n";

    return 0;
}

Time Complexity: O(log₂n)
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 y
int 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 code
int main()
{
    int x = 2, y = 1, z = 3;

    // Funtion call for test case 1
    cout << maxTriplets(x, y, z) << "\n";

    x = 3, y = 4, z = 1;

    // Funtion call for test case 2
    cout << maxTriplets(x, y, z) << "\n";

    return 0;
}

Time Complexity: O(1)
Auxiliary Space: O(1)