Attractive triplets

Solution Approach

The brute force solution idea is very straightforward, and we will discuss that here. The idea is to traverse through all the triplets possible and check if it satisfies the given conditions or not. If yes, we will increase the answer by one since one more such triplet is found. In the end, we will print the answer. 

Note: The value of z can be from 1 to n. The value of y can be from z to n. The value of x will be n-(y+z). By doing so, we are making sure that the first two conditions are already satisfied for that set of x, y, and z. We only need to check if 0<=x<=n, y<=x, and |x-y-z| >k or not. 

The steps of implementation are:

• Input the values of n and k.
• Declare and initialize a variable called "ans," which will store triplets' count that follows the given conditions.
• Run two nested loops, one for z, and one for y. Find the value of x corresponding to a value of y, and z. For a triplet {x, y, z}, check for the conditions. We will start the values of y for a given z from z to n so that one condition z<=y is already satisfied.
• Find the value of x corresponding to the taken value of y and z.
• Check if 0<=x<=n and y<=x.
• Check if the triplet {x, y, z} satisfies the condition |x-y-z| > k. If yes, increase the value of the answer by 1.
• Print the answer.

C++ implementation

#include <bits/stdc++.h>
using namespace std;

int main() {

    /* Input the values of n and k. */
    int n,k;
    n=12,k=3;

    /* Declare and initialize a variable called "ans", which will store the count of triplets that follow the given conditions. */
    int ans = 0;
    
    /* Run two nested loops, one for z, and one for y. Find the value of x corresponding to a value of y, and z. For a triplet {x, y, z}, check for the conditions. We will start the values of y for a given z from z to n so that one condition z<=y is already satisfied. */
    for(int z = 1; z <= n; z++){
        for(int y = z; y <= n; y++){

            /* Find the value of x corresponding to the taken value of y and z. */
            int x = n-(y+z);

            /* Check if 0<=x<=n and y<=x. */
            if(0<=x && x<=n && y<=x){
                    
                /* Check if the triplet {x, y, z} satisfies the condition |x-y-z| > k. If yes, increase the value of answer by 1. */
                if(abs(x-y-z)>k){
                    ans++;
                }
            }
        }
    }
    /* Print the answer */
    cout<<ans<<endl;
}

Output

5

Complexities

Time complexity

O(n²), where n is the value in the input

Reason: We’re running two nested loops for the values of y and z. This takes O(n²). Rest all the operations take constant time. Thus, the total time complexity is O(n²).

Space complexity

O(1)

Reason: All the spaces taken are constant.

FAQs

1. What is a triplet?
   A triplet is a collection of three objects. It is represented as {x, y, z}, where x, y, and z are the objects. It is called a tuple.
    
2. What is the general way to find a number in a range that follows the condition given a condition?
   The general way to find such a number is to traverse the given range and for each number in the range, check whether the number follows the given condition or not. If yes, then we found the required number.
    
3. What is a pair?
   A pair is a collection of two objects. It is represented as {x,y}, where x and y are the objects.
    
4. What is the difference between a pair and a triplet?
   The difference between a pair and a triplet is that the size of a triplet is three, whereas that of a pair is only two.
    
5. If two numbers, x, and y, are given, and x, y, and z follow x+y+z = n, then how do we find z?
   Since the numbers x, y, and z follow x+y+z = n, if we know x and y, we can find z as z = n- (x+y).

Key Takeaways

In this article, we learned how to solve the problem of “Attractive triplets”. The approach discussed here has a time complexity of O(n^2). You can now try to optimize the solution further. 

Are you planning to ace the interviews of reputed product-based companies like Amazon, Google, Microsoft, and more? 

Attempt our Online Mock Test Series on Coding Ninjas Studio now!

Happy Coding!