Count of Triplets – Decreasing Order
Count the number of triplets in an array where three integers appear in strictly decreasing order.
Understand the Problem
Problem Statement
Count of Triplets – Decreasing Order: The program must accept N integers as the input. The program must print the count of triplets where the three integers are in strictly decreasing order among the given N integers as the output.
Note: The order of integers in the triplets must be in the same order as in the input.
Constraints
- 3 ≤ N ≤ 100
- 1 ≤ Each integer value ≤ 10^5
Examples
5
7 2 8 3 13The 3 valid triplets are: (7, 2, 1), (7, 3, 1), and (8, 3, 1). All these triplets have integers in strictly decreasing order while maintaining their relative positions from the original array.
9
75 82 23 44 81 91 72 24 928There are 8 valid triplets in this array where three integers appear in strictly decreasing order while maintaining their relative positions.
Solution
#include <stdio.h>
int main() {
int N;
scanf("%d", &N);
int arr[N];
for (int i = 0; i < N; i++) {
scanf("%d", &arr[i]);
}
int count = 0;
// Check all possible triplets
for (int i = 0; i < N; i++) {
for (int j = i + 1; j < N; j++) {
for (int k = j + 1; k < N; k++) {
if (arr[i] > arr[j] && arr[j] > arr[k]) {
count++;
}
}
}
}
printf("%d\n", count);
return 0;
}The C solution follows the same brute-force approach. We first read N and the array elements using scanf. Then we use three nested for loops to iterate through all possible triplets (i, j, k) where i < j < k. For each triplet, we check if arr[i] > arr[j] > arr[k] using the condition in the if statement. If true, we increment the counter. Finally, we print the total count using printf.