Count of triplets in an Array (i, j, k) such that i < j < k and a[k] < a[i] < a[j] - GeeksforGeeks (2023)

Given an array arr[] of N integers, the task is to count number of triplets (i, j, k) in the array such that a[k] < a[i] < a[j] and i < j < k.
Examples:

Input: arr[] = {2, 5, 1, 3, 0}
Output: 4
Explanation:
Below are the triplets (i, j, k) such that i < j < k and a[k] < a[i] < a[j]:
1. (0, 1, 2) and arr[2] < arr[0] 1 < 2 < 5.
2. (0, 1, 4) and arr[4] < arr[0] 0 < 2 < 5.
3. (0, 3, 4) and arr[4] < arr[0] 0 < 2 < 3.
4. (2, 3, 4) and arr[4] < arr[2] 0 < 1 < 3.
Input: arr[] = {2, 5, 1, 2, 0, 3, 10, 1, 5, 0 }
Output: 25

Recommended: Please try your approach on {IDE} first, before moving on to the solution.

Naive Approach: The idea is to iterate 3 loops and check for each triplet (i, j, k) satisfy the given conditions or not. If yes then increment for that triplet and print the final count after checking all the triplets.

Below is the implementation of the above approach:

C++

`// C++ program for the above approach`

`#include <bits/stdc++.h>`

`using` `namespace` `std;`

`// Function to count triplets with the`

`// given conditions`

`int` `CountTriplets(``int` `arr[], ``int` `n)`

`{`

`int` `cnt = 0;`

`for` `(``int` `i = 0; i < n; i++)`

`for` `(``int` `j = i + 1; j < n; j++)`

`for` `(``int` `k = j + 1; k < n; k++)`

`// If it satisfy the`

`// given conditions`

`if` `(arr[k] < arr[i]`

`&& arr[i] < arr[j]) {`

`cnt += 1;`

`}`

`// Return the final count`

`return` `cnt;`

`}`

`// Driver Code`

`int` `main()`

`{`

`// Given array arr[]`

`int` `arr[] = { 2, 5, 1, 3, 0 };`

`int` `n = ``sizeof``(arr) / ``sizeof``(arr[0]);`

`// Function Call`

`cout << CountTriplets(arr, n)`

`<< endl;`

`return` `0;`

`}`

Java

`// Java program for the above approach`

`class` `GFG{`

`// Function to count triplets`

`// with the given conditions`

`static` `int` `CountTriplets(``int` `arr[], ``int` `n)`

`{`

`int` `cnt = ``0``;`

`for``(``int` `i = ``0``; i < n; i++)`

`for``(``int` `j = i + ``1``; j < n; j++)`

`for``(``int` `k = j + ``1``; k < n; k++)`

`// If it satisfy the`

`// given conditions`

`if` `(arr[k] < arr[i] &&`

`arr[i] < arr[j])`

`{`

`cnt += ``1``;`

`}`

`// Return the final count`

`return` `cnt;`

`}`

`// Driver Code`

`public` `static` `void` `main(String[] args)`

`{`

`// Given array arr[]`

`int` `arr[] = ``new` `int``[]{ ``2``, ``5``, ``1``, ``3``, ``0` `};`

`int` `n = arr.length;`

`System.out.print(CountTriplets(arr, n));`

`}`

`}`

`// This code is contributed by Pratima Pandey`

(Video) Arrays 2: Count The Triplets | Must Do Coding Questions | Interview Preparation | GeeksForGeeks

Python3

`# Python3 program for the above approach`

`# Function to count triplets with the`

`# given conditions`

`def` `CountTriplets(arr, n):`

`cnt ``=` `0``;`

`for` `i ``in` `range``(``0``, n):`

`for` `j ``in` `range``(i ``+` `1``, n):`

`for` `k ``in` `range``(j ``+` `1``, n):`

`# If it satisfy the`

`# given conditions`

`if` `(arr[k] < arr[i] ``and` `arr[i] < arr[j]):`

`cnt ``+``=` `1``;`

`# Return the final count`

`return` `cnt;`

`# Driver Code`

`# Given array arr[]`

`arr ``=` `[ ``2``, ``5``, ``1``, ``3``, ``0` `];`

`n ``=` `len``(arr);`

`# Function Call`

`print``(CountTriplets(arr, n))`

`# This code is contributed by Code_Mech`

C#

`// C# program for the above approach`

`using` `System;`

`class` `GFG{`

`// Function to count triplets`

`// with the given conditions`

`static` `int` `CountTriplets(``int` `[]arr, ``int` `n)`

`{`

`int` `cnt = 0;`

`for``(``int` `i = 0; i < n; i++)`

`for``(``int` `j = i + 1; j < n; j++)`

`for``(``int` `k = j + 1; k < n; k++)`

`// If it satisfy the`

`// given conditions`

`if` `(arr[k] < arr[i] &&`

`arr[i] < arr[j])`

`{`

`cnt += 1;`

`}`

`// Return the final count`

`return` `cnt;`

`}`

`// Driver Code`

`public` `static` `void` `Main(``string``[] args)`

`{`

`// Given array arr[]`

`int` `[]arr = ``new` `int``[]{ 2, 5, 1, 3, 0 };`

`int` `n = arr.Length;`

`Console.Write(CountTriplets(arr, n));`

`}`

`}`

`// This code is contributed by Ritik Bansal`

Javascript

`<script>`

`// Javascript program for the above approach`

`// Function to count triplets with the`

`// given conditions`

`function` `CountTriplets(arr, n)`

`{`

`let cnt = 0;`

`for` `(let i = 0; i < n; i++)`

`for` `(let j = i + 1; j < n; j++)`

`for` `(let k = j + 1; k < n; k++)`

`// If it satisfy the`

`// given conditions`

`if` `(arr[k] < arr[i]`

`&& arr[i] < arr[j]) {`

`cnt += 1;`

`}`

`// Return the final count`

`return` `cnt;`

`}`

`// Given array arr[]`

`let arr = [ 2, 5, 1, 3, 0 ];`

`let n = arr.length;`

`// Function Call`

`document.write(CountTriplets(arr, n));`

`</script>`

(Video) Counting the triplets

Output:

`4`

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

Efficient Approach: We can reduce the complexity from N^3 to N^2, using the below steps:

1. Run two loops to find pairs (i, j) such that i < j and arr[j] > arr[i] and keep the count of these pairs as cnt.
2. While in the above loop if there exists any element such arr[j] < arr[i] then increment the count of triplets by cnt as the current element is the Kth element such that a[k] < a[i] < a[j] for triplet i < j < k.

Below is the implementation of the above approach:

C++

`// C++ program for the above approach`

`#include <bits/stdc++.h>`

`using` `namespace` `std;`

`// Function to count triplets`

`int` `CountTriplets(``int` `a[], ``int` `n)`

`{`

`// To store count of total triplets`

`int` `ans = 0;`

`for` `(``int` `i = 0; i < n; i++) {`

`// Initialize count to zero`

`int` `cnt = 0;`

`for` `(``int` `j = i + 1; j < n; j++) {`

`// If a[j] > a[i] then,`

`// increment cnt`

`if` `(a[j] > a[i])`

`cnt++;`

`// If a[j] < a[i], then`

`// it mean we have found a[k]`

`// such that a[k] < a[i] < a[j]`

`else`

`ans += cnt;`

`}`

`}`

`// Return the final count`

`return` `ans;`

`}`

`// Driver code`

`int` `main()`

`{`

`int` `arr[] = { 2, 5, 1, 3, 0 };`

`int` `n = ``sizeof``(arr) / ``sizeof``(arr[0]);`

`cout << CountTriplets(arr, n) << endl;`

`return` `0;`

`}`

Java

`// Java program for the above approach`

`class` `GFG{`

`// Function to count triplets`

`static` `int` `CountTriplets(``int` `a[], ``int` `n)`

`{`

`// To store count of total triplets`

`int` `ans = ``0``;`

`for` `(``int` `i = ``0``; i < n; i++)`

`{`

`// Initialize count to zero`

`int` `cnt = ``0``;`

`for` `(``int` `j = i + ``1``; j < n; j++)`

`{`

`// If a[j] > a[i] then,`

`// increment cnt`

`if` `(a[j] > a[i])`

`cnt++;`

`// If a[j] < a[i], then`

`// it mean we have found a[k]`

`// such that a[k] < a[i] < a[j]`

`else`

`ans += cnt;`

`}`

`}`

`// Return the final count`

`return` `ans;`

`}`

`// Driver code`

`public` `static` `void` `main(String[] args)`

`{`

`int` `arr[] = { ``2``, ``5``, ``1``, ``3``, ``0` `};`

`int` `n = arr.length;`

`System.out.print(CountTriplets(arr, n));`

`}`

`}`

`// This code is contributed by shivanisinghss2110`

(Video) Triplet Sum in an Array | Data Structures & Algorithms | Programming Tutorials | GeeksforGeeks

Python3

`# Python3 program for`

`# the above approach`

`# Function to count triplets`

`def` `CountTriplets(a, n):`

`# To store count`

`# of total triplets`

`ans ``=` `0`

`for` `i ``in` `range` `(n):`

`# Initialize count to zero`

`cnt ``=` `0`

`for` `j ``in` `range` `(i ``+` `1` `, n):`

`# If a[j] > a[i] then,`

`# increment cnt`

`if` `(a[j] > a[i]):`

`cnt ``+``=` `1`

`# If a[j] < a[i], then`

`# it mean we have found a[k]`

`# such that a[k] < a[i] < a[j]`

`else``:`

`ans ``+``=` `cnt`

`# Return the final count`

`return` `ans`

`# Driver code`

`if` `__name__ ``=``=` `"__main__"``:`

`arr ``=` `[``2``, ``5``, ``1``, ``3``, ``0``]`

`n ``=` `len``(arr)`

`print` `(CountTriplets(arr, n))`

`# This code is contributed by Chitranayal`

C#

`// C# program for the above approach`

(Video) Max Triplet Sum | Arrays | GFG | Algorithm Explanation by alGOds

`using` `System;`

`class` `GFG{`

`// Function to count triplets`

`static` `int` `CountTriplets(``int` `[]a, ``int` `n)`

`{`

`// To store count of total triplets`

`int` `ans = 0;`

`for` `(``int` `i = 0; i < n; i++)`

`{`

`// Initialize count to zero`

`int` `cnt = 0;`

`for` `(``int` `j = i + 1; j < n; j++)`

`{`

`// If a[j] > a[i] then,`

`// increment cnt`

`if` `(a[j] > a[i])`

`cnt++;`

`// If a[j] < a[i], then`

`// it mean we have found a[k]`

`// such that a[k] < a[i] < a[j]`

`else`

`ans += cnt;`

`}`

`}`

`// Return the final count`

`return` `ans;`

`}`

`// Driver code`

`public` `static` `void` `Main()`

`{`

`int` `[]arr = { 2, 5, 1, 3, 0 };`

`int` `n = arr.Length;`

`Console.Write(CountTriplets(arr, n));`

`}`

`}`

`// This code is contributed by Code_Mech`

Javascript

`<script>`

`// Javascript program for the above approach`

`// Function to count triplets`

`function` `CountTriplets(a, n)`

`{`

`// To store count of total triplets`

`let ans = 0;`

`for``(let i = 0; i < n; i++)`

`{`

`// Initialize count to zero`

`let cnt = 0;`

`for``(let j = i + 1; j < n; j++)`

`{`

`// If a[j] > a[i] then,`

`// increment cnt`

`if` `(a[j] > a[i])`

`cnt++;`

`// If a[j] < a[i], then`

`// it mean we have found a[k]`

`// such that a[k] < a[i] < a[j]`

`else`

`ans += cnt;`

`}`

`}`

`// Return the final count`

`return` `ans;`

`}`

`// Driver code`

`let arr = [ 2, 5, 1, 3, 0 ];`

`let n = arr.length;`

`document.write(CountTriplets(arr, n));`

`// This code is contributed by rameshtravel07`

`</script>`

Output:

`4`

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

My Personal Notesarrow_drop_up

FAQs

How do you count triplets in an array? ›

Take the initial variable count as 0 for the number of triplets. Traverse array using three for loops for each element of the triplet. Outermost loop from 0<=i<n-2, inner loop i<j<n-1, innermost j<k<n. Check if arr[i]+arr[j]==arr[k] or arr[i]+arr[k]==arr[j] or arr[k]+arr[j]==arr[i] If true then increment count.

How do you find array triplets with sum of two elements equals third? ›

1) Brute Force Method

In this method, we check every combination of triplets of the given array for the sum of any two elements equals to third element. There will be three for loops with three indices – i (from 0 to inputArray. length-2 ), j (from i+1 to inputArray. length-1 ) and k (from j+1 to inputArray.

How many combinations of triplets are possible? ›

So, the correct answer is '64'.

How do you find the triplet of an array in Python? ›

Algorithm
1. Sort the given array in ascending order.
2. Check if triplet is formed by nums[i] and a pair from subarray nums[i+1…n].
3. Maintain two indices pointing to endpoints of the subarray nums[i+1…n].
4. Construct a while loop if low is less than high. ...
5. Print the triplet, if the given target is found.
Nov 6, 2022

How do you count triplets fast? ›

Begin by counting an ordinary eighth note pulse as "one-and-two-and-three-and-four-and." Then, use similar language to count the three pulses of a triplet by saying "tri-pa-let" as you play—for instance, "one-and-two-and-tri-pa-let-four-and." You can also count a triplet beat by including the number of the beat—for ...

What is the triplet rule? ›

Here, we examine a triplet rule (i.e., a rule which considers sets of three spikes, i.e., two pre and one post or one pre and two post) and compare it to classical pair-based STDP learning rules.

How do you find the number of triplets? ›

If the triplet is (x, x, 2x), add freq[x]C2 * freq[2x]C1 to count. If the triplet is (x, y, x + y), add freq[x]C1 * freq[y]C1 * freq[x + y]C1 to count.

How do you find the number of ordered triplets? ›

1. The number of ordered triplets of positive integers which are solutions of the equation x+y+z=100 is.
2. The number of ordered triplets of non-negative integers which are solutions of the equation x + y + z = 100 is.
3. the number of ordered triplets(x,y,z) such that (x+y)(y+z)(z+x)=2013, where x,y,z are integers, is.

What is triplet with sum k in array? ›

An array is said to have a triplet {ARR[i], ARR[j], ARR[k]} with sum = 'K' if there exists three indices i, j and k such that i!= j, j!= k and i!= j and ARR[i] + ARR[j] + ARR[k] = 'K'.

What is triplet sum in array? ›

Input: array = {12, 3, 4, 1, 6, 9}, sum = 24; Output: 12, 3, 9. Explanation: There is a triplet (12, 3 and 9) present. in the array whose sum is 24. Input: array = {1, 2, 3, 4, 5}, sum = 9.

What are the 3 types of triplets? ›

Triplets can be:
• Trichorionic. Each baby has its own placenta and chorion.
• Dichorionic. Two of the babies share a placenta and chorion and the other is separate.
• Monochorionic. All three babies share the same placenta and chorion.
• In separate amniotic sacs, or two or more babies can share an amniotic sac.
Mar 17, 2020

How do you find the multiples of a number in an array? ›

Simple Approach is to traverse over every value of 'k' in whole array and count total multiples by checking modulus of every element of array i.e., for every element of i (0 < i < n), check whether arr[i] % k == 0 or not. If it's perfectly divisible of k, then increment count.

What is the probability of getting a triplet? ›

Naturally, twins occur in about one in 250 pregnancies, triplets in about one in 10,000 pregnancies, and quadruplets in about one in 700,000 pregnancies.

What are examples of triples? ›

The most well known examples are (3,4,5) and (5,12,13). Notice we can multiple the entries in a triple by any integer and get another triple. For example (6,8,10), (9,12,15) and (15,20,25). The triples for which the entries are relatively prime are called primitive.

How do you count triplets in 3 4 time? ›

The time signature is 3/4, so each bar needs to have an equivalent of three crotchet (quarter note) beats. Each "3" symbol shows a triplet group. One triplet group is worth one crotchet. The quavers (8th notes) beamed in twos are also worth one crotchet each.

What are the 5 most common Pythagorean triples? ›

The 5 most common Pythagorean triples are ( 3 , 4 , 5 ) , ( 5 , 12 , 13 ) , ( 6 , 8 , 10 ) , ( 9 , 12 , 15 ) , and ( 15 , 20 , 25 ) .

What are all Pythagoras triplets? ›

The 5 most common Pythagorean triples are (3, 4, 5), (5, 12, 13), (6, 8, 10), (9, 12, 15), and (15, 20, 25).

How do you find Pythagorean triples if one number is given? ›

If a number (n) odd is given, then the Pythagorean triples are of the form, (n, (n2/2 - 0.5) and (n2/2 + 0.5)). If a number (n) even is given, then the Pythagorean triples are of the form = n, (n/2)2-1), ((n/2)2+1).

How do you solve systems with ordered triples? ›

To check that an ordered triple is a solution, substitute in the corresponding x-, y-, and z-values and then simplify to see if you obtain a true statement from all three equations. Because the ordered triple satisfies all three equations we conclude that it is indeed a solution.

How do you write triplets in logic? ›

The most common tuplet is the triplet (a group of three notes that typically occupies the space of two or four notes).
...
Insert tuplets with the pointer
1. Insert the first note where you want it to appear in the score.
2. Drag the N-tuplet symbol onto it. ...
3. Define the settings in the Tuplet window.

What is the value of triplets? ›

The triplet is a musical symbol, which alters the time value of notes and rests. It says to the reader: "fit three time values of these notes and/or rests, into the same time value of two notes and/or rests". Each note and/or rest (member of a triplet group) has an value equal to . 66 of it's original value.

What is K value in array? ›

The k Strongest Values in an Array in C++

So we have to find a list of the strongest k values in the array. So, if the input is like arr = [1,2,3,4,5], k = 2, then the output will be [5,1], this is because median is 3, and the elements of the array sorted by the strongest are [5,1,4,2,3].

What is a triplet of three numbers? ›

Pythagorean triples are a2+b2 = c2 where a, b and c are the three positive integers. These triples are represented as (a,b,c). Here, a is the perpendicular, b is the base and c is the hypotenuse of the right-angled triangle. The most known and smallest triplets are (3,4,5).

What are 4 triplets called? ›

What are 7 triplets called? ›

1.5 Sextuplets (6) 1.6 Septuplets (7) 1.7 Octuplets (8)

Can all 3 triplets be identical? ›

Though triplets are most commonly fraternal (dizygotic or trizygotic), it is possible for triplets to be identical (monozygotic).

How do you find three multiples? ›

The multiples of the number 3 can be calculated by multiplying integers. For example, to calculate the Multiples of 3 we will use the product of 3 with the natural numbers 1, 2, 3, .......... and thus will get 3 x 1, 3 x 2, 3 x 3, 3 x 4, 3 x 5, etc., which equal 3, 6, 9, 12, 15, etc.

What is the sequence of multiples of 3? ›

The first ten multiples of 3 are listed below: 3, 6, 9, 12, 15, 18, 21, 24, 27, 30.

What are the odds of having 3 sets of triplets? ›

Q: What are the odds of having a multiple birth?
Twins1 in 250 pregnancies
Triplets1 in 62,500 pregnancies
Quintuplets1 in 3,906,250,000 pregnancies
Sep 23, 2019

Is it possible to have 2 sets of triplets? ›

According to health experts, the odds of conceiving triplets naturally is one in 9,000 and the odds of it happening twice is one in 64 million.

What is the probability of getting a multiple of 3? ›

probability of gettting multiples of 3=62=31.

Does tripled mean times 3? ›

Triple means to multiply by three. If you triple the number two, you get six, and six is the triple of the number two.

How do you write ordered triples? ›

Ordered Triples

An ordered triple is a list of 3 elements written in a certain order. As with ordered pairs, order is important. For example, the numbers 1, 2 and 3 can form 6 ordered triples: (1,2,3), (1,3,2), (2,1,3), (2,3,1), (3,1,2), (3,2,1).

What is the rule of three or tripling? ›

The Rule of Three is a powerful technique or principle required for writing or speaking. It states that any ideas, thoughts, events, characters or sentences that are presented in threes are more effective and memorable. Hence, it is called the Rule of Three.

Is triplets the same as 3 4? ›

Add the missing bar lines to this tune. The time signature is 3/4, so each bar needs to have an equivalent of three crotchet (quarter note) beats. Each "3" symbol shows a triplet group. One triplet group is worth one crotchet.

What is the formula for finding triplets? ›

Pythagorean triples are a2+b2 = c2 where a, b and c are the three positive integers. These triples are represented as (a,b,c). Here, a is the perpendicular, b is the base and c is the hypotenuse of the right-angled triangle. The most known and smallest triplets are (3,4,5).

How do you check for triplets? ›

How to Form a Pythagorean Triplet
1. If the number is odd: Square the number N and then divide it by 2. Take the integer that is immediately before and after that number i.e. (N2/2 -0.5) and (N2/2 +0.5). ...
2. If the number is even: Take the half of that number N and then square it. Pythagorean triplet= N, (N/2)2-1, (N/2)2+1.

What is the probability of getting triplets? ›

Naturally, twins occur in about one in 250 pregnancies, triplets in about one in 10,000 pregnancies, and quadruplets in about one in 700,000 pregnancies.

What is a triples example? ›

A triple consists of three components: A subject, a predicate, and an object. For example, we might say: :john a :Doctor . This triple can be broken down like this: Subject : John.

How do you solve a 3 sum problem? ›

Given a solver for 3SUM, the Conv3SUM problem can be solved in the following way.
1. Define a new array T, such that for every index i: (where n is the number of elements in the array, and the indices run from 0 to n-1).
2. Solve 3SUM on the array T.

How do I combine 3 arrays? ›

Merge 3 Sorted Arrays by merging Two Arrays at a time:
1. First, merge the arr1 and arr2 using the idea mentioned in Merge Two Sorted Arrays.
2. Now merge the resultant array (from arr1 and arr2) with arr3.
Jan 17, 2023

How many is a triplet? ›

Triplets split a beat into three equal parts. We may also encounter other, less common, tuplets, such as quintuplets (5), sextuplets (6), and so on. Note: Eighth note triplets are the most common, and what we'll be focusing on here.

Can triplets marry triplets? ›

The odds of having triplets is about 1 in 9,000 births. Imagine the odds of those triplets marrying another set of triplets, that's just plain awesome! We love that these couples have found their way to each other and will share this special bond with a spouse who understands what life is like as a multiple!

What are 6 triplets called? ›

Sextuplets

Videos

1. Count the Triplet | Competitive Programming | Array | Data Structures
(Coding By Fun)
2. Pythagorean Triplet in an array | GeeksforGeeks
(GeeksforGeeks)
3. Increasing Triplet Subsequence | Live Coding with Explanation | Leetcode #334
4. HackerRank Interview Prep - Problem 13: Count Triplets
(Brian Dyck)
5. Magic Triplets | Easiest Solution💥😃Problem of the Day #geeksforgeeks#leetcode
(CODE with Rahul.)
6. Maximum triplet sum such that A[i] less than A[j] less than A[k] - With code walkthrough in Java
(CSE Insights)
Top Articles
Latest Posts
Article information

Author: Aron Pacocha

Last Updated: 04/21/2023

Views: 5729

Rating: 4.8 / 5 (68 voted)

Author information

Name: Aron Pacocha

Birthday: 1999-08-12

Address: 3808 Moen Corner, Gorczanyport, FL 67364-2074

Phone: +393457723392

Job: Retail Consultant

Hobby: Jewelry making, Cooking, Gaming, Reading, Juggling, Cabaret, Origami

Introduction: My name is Aron Pacocha, I am a happy, tasty, innocent, proud, talented, courageous, magnificent person who loves writing and wants to share my knowledge and understanding with you.