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
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>
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:
- 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.
- 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
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
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.
So, the correct answer is '64'.
How do you find the triplet of an array in Python? ›- Sort the given array in ascending order.
- Check if triplet is formed by nums[i] and a pair from subarray nums[i+1…n].
- Maintain two indices pointing to endpoints of the subarray nums[i+1…n].
- Construct a while loop if low is less than high. ...
- Print the triplet, if the given target is found.
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? ›- The number of ordered triplets of positive integers which are solutions of the equation x+y+z=100 is.
- The number of ordered triplets of non-negative integers which are solutions of the equation x + y + z = 100 is.
- the number of ordered triplets(x,y,z) such that (x+y)(y+z)(z+x)=2013, where x,y,z are integers, is.
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? ›
- 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.
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? ›...
Insert tuplets with the pointer
- Insert the first note where you want it to appear in the score.
- Drag the N-tuplet symbol onto it. ...
- 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].
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? ›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? ›| Twins | 1 in 250 pregnancies |
|---|---|
| Triplets | 1 in 62,500 pregnancies |
| Quadruplets | 1 in 15,625,000 pregnancies |
| Quintuplets | 1 in 3,906,250,000 pregnancies |
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).
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? ›Adding Bar Lines with Triplets
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.
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? ›- 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). ...
- 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.
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? ›- 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).
- Solve 3SUM on the array T.
How do I combine 3 arrays? ›
- First, merge the arr1 and arr2 using the idea mentioned in Merge Two Sorted Arrays.
- Now merge the resultant array (from arr1 and arr2) with arr3.
- Print the answer array.
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? ›