Given an array of positive integers. We need to find how many triples of indices (i, j, k) (i < j < k), such that a[i] * a[j] * a[k] is minimum possible.
Examples:
Input : 5
1 3 2 3 4
Output : 2
The triplets are (1, 3, 2)
and (1, 2, 3)
Input : 5
2 2 2 2 2
Output : 5
In this example we choose three 2s
out of five, and the number of ways
to choose them is 5C3.
Input : 6
1 3 3 1 3 2
Output : 1
There is only one way (1, 1, 2).
Following cases arise in this problem.
- All three minimum elements are same. For example {1, 1, 1, 1, 2, 3, 4}. The solution for such cases is nC3.
- Two elements are same. For example {1, 2, 2, 2, 3} or {1, 1, 2, 2}. In this case, count of occurrences of first (or minimum element) cannot be more than 2. If minimum element appears two times, then answer is count of second element (We get to choose only 1 from all occurrences of second element. If minimum element appears once, the count is nC2.
- All three elements are distinct. For example {1, 2, 3, 3, 5}. In this case, answer is count of occurrences of third element (or nC1).
We first sort the array in increasing order. Then count the frequency of 3 element of 3rd element from starting. Let the frequency be ‘count’. Following cases arise.
- If 3rd element is equal to the first element, no. of triples will be (count-2)*(count-1)*(count)/6, where count is the frequency of 3rd element.
- If 3rd element is equal to 2nd element, no. of triples will be (count-1)*(count)/2. Otherwise no. of triples will be value of count.
Implementation:
C++
// CPP program to count number of ways we can// form triplets with minimum product.#include <bits/stdc++.h>using namespace std;// function to calculate number of tripleslong long noOfTriples(long long arr[], int n){ // Sort the array sort(arr, arr + n); // Count occurrences of third element long long count = 0; for (long long i = 0; i < n; i++) if (arr[i] == arr[2]) count++; // If all three elements are same (minimum // element appears at least 3 times). Answer // is nC3. if (arr[0] == arr[2]) return (count - 2) * (count - 1) * (count) / 6; // If minimum element appears once. // Answer is nC2. else if (arr[1] == arr[2]) return (count - 1) * (count) / 2; // Minimum two elements are distinct. // Answer is nC1. return count;}// Driver codeint main(){ long long arr[] = { 1, 3, 3, 4 }; int n = sizeof(arr) / sizeof(arr[0]); cout << noOfTriples(arr, n); return 0;} |
Java
// Java program to count number of ways we can// form triplets with minimum product.import java.util.Arrays;class GFG { // function to calculate number of triples static long noOfTriples(long arr[], int n) { // Sort the array Arrays.sort(arr); // Count occurrences of third element long count = 0; for (int i = 0; i < n; i++) if (arr[i] == arr[2]) count++; // If all three elements are same (minimum // element appears at least 3 times). Answer // is nC3. if (arr[0] == arr[2]) return (count - 2) * (count - 1) * (count) / 6; // If minimum element appears once. // Answer is nC2. else if (arr[1] == arr[2]) return (count - 1) * (count) / 2; // Minimum two elements are distinct. // Answer is nC1. return count; } //driver code public static void main(String arg[]) { long arr[] = { 1, 3, 3, 4 }; int n = arr.length; System.out.print(noOfTriples(arr, n)); }}// This code is contributed by Anant Agarwal. |
Python3
# Python3 program to count number# of ways we can form triplets # with minimum product.# function to calculate number of triplesdef noOfTriples (arr, n): # Sort the array arr.sort() # Count occurrences of third element count = 0 for i in range(n): if arr[i] == arr[2]: count+=1 # If all three elements are same # (minimum element appears at l # east 3 times). Answer is nC3. if arr[0] == arr[2]: return (count - 2) * (count - 1) * (count) / 6 # If minimum element appears once. # Answer is nC2. elif arr[1] == arr[2]: return (count - 1) * (count) / 2 # Minimum two elements are distinct. # Answer is nC1. return count # Driver codearr = [1, 3, 3, 4]n = len(arr)print (noOfTriples(arr, n))# This code is contributed by "Abhishek Sharma 44" |
C#
// C# program to count number of ways// we can form triplets with minimum product.using System;class GFG { // function to calculate number of triplesstatic long noOfTriples(long []arr, int n){ // Sort the array Array.Sort(arr); // Count occurrences of third element long count = 0; for (int i = 0; i < n; i++) if (arr[i] == arr[2]) count++; // If all three elements are same (minimum // element appears at least 3 times). Answer // is nC3. if (arr[0] == arr[2]) return (count - 2) * (count - 1) * (count) / 6; // If minimum element appears once. // Answer is nC2. else if (arr[1] == arr[2]) return (count - 1) * (count) / 2; // Minimum two elements are distinct. // Answer is nC1. return count;}//driver codepublic static void Main(){ long []arr = { 1, 3, 3, 4 }; int n = arr.Length; Console.Write(noOfTriples(arr, n));}}//This code is contributed by Anant Agarwal. |
Javascript
<script> // Javascript program to count number of ways we can // form triplets with minimum product. // function to calculate number of triples function noOfTriples(arr, n) { // Sort the array arr.sort(); // Count occurrences of third element let count = 0; for (let i = 0; i < n; i++) if (arr[i] == arr[2]) count++; // If all three elements are same (minimum // element appears at least 3 times). Answer // is nC3. if (arr[0] == arr[2]) return (count - 2) * (count - 1) * (count) / 6; // If minimum element appears once. // Answer is nC2. else if (arr[1] == arr[2]) return (count - 1) * (count) / 2; // Minimum two elements are distinct. // Answer is nC1. return count; } let arr = [ 1, 3, 3, 4 ]; let n = arr.length; document.write(noOfTriples(arr, n)); // This code is contributed by mukesh07.</script> |
PHP
<?php// PHP program to count number of ways // we can form triplets with minimum// product.// function to calculate number of// triplesfunction noOfTriples( $arr, $n){ // Sort the array sort($arr); // Count occurrences of third element $count = 0; for ( $i = 0; $i < $n; $i++) if ($arr[$i] == $arr[2]) $count++; // If all three elements are same // (minimum element appears at least // 3 times). Answer is nC3. if ($arr[0] == $arr[2]) return ($count - 2) * ($count - 1) * ($count) / 6; // If minimum element appears once. // Answer is nC2. else if ($arr[1] == $arr[2]) return ($count - 1) * ($count) / 2; // Minimum two elements are distinct. // Answer is nC1. return $count;}// Driver code $arr = array( 1, 3, 3, 4 ); $n = count($arr); echo noOfTriples($arr, $n);// This code is contributed by anuj_67.?> |
Output
1
Time Complexity: O(n Log n)
Auxiliary Space: O(1)
The solution can be optimized by first finding minimum element and its frequency and if frequency is less than 3, then finding second minimum and its frequency. If overall frequency is less than 3, then finding third minimum and its frequency. Time complexity of this optimized solution would be O(n)
Approach Using Dp :
C++
#include <bits/stdc++.h>using namespace std;const int N = 1005;long long dp[N][N];long long noOfTriples(long long arr[], int n) { sort(arr, arr + n); memset(dp, 0, sizeof(dp)); dp[0][arr[0]] = 1; for (int i = 1; i < n; i++) { dp[i][arr[i]] = 1; for (int j = arr[i-1]+1; j < arr[i]; j++) { dp[i][j] = dp[i-1][j]; } if (arr[i] == arr[1]) { for (int j = arr[1]; j <= arr[2]; j++) { dp[i][arr[i]] += dp[i-1][j] * (i-1) * (i-2) / 2; } } else if (arr[i] == arr[2]) { dp[i][arr[i]] = dp[i-1][arr[i]] * (i-1) * (i-2) / 6; for (int j = arr[2]; j < N; j++) { dp[i][j] += dp[i-1][j]; } } else { for (int j = arr[2]; j < N; j++) { dp[i][j] += dp[i-1][j]; } } } long long ans = 0; for (int j = arr[0]; j <= arr[2]; j++) { ans += dp[n-1][j]; } return ans;}int main() { long long arr[] = { 1, 3, 3, 4 }; int n = sizeof(arr) / sizeof(arr[0]); cout << noOfTriples(arr, n); return 0;} |
Java
import java.util.Arrays;public class GFG { static final int N = 1005; static long[][] dp = new long[N][N]; // Function to count the number of triples in the array static long noOfTriples(long[] arr, int n) { // Sort the array in non-decreasing order Arrays.sort(arr); // Initialize the dp array to store intermediate results for (int i = 0; i < N; i++) { Arrays.fill(dp[i], 0); } dp[0][(int) arr[0]] = 1; // Iterate through the array elements for (int i = 1; i < n; i++) { // Update dp for the current element dp[i][(int) arr[i]] = 1; // Fill the dp array for values between the previous element and the current element for (int j = (int) arr[i - 1] + 1; j < arr[i]; j++) { dp[i][j] = dp[i - 1][j]; } // Handle special cases when the current element is equal to arr[1] or arr[2] if (arr[i] == arr[1]) { for (int j = (int) arr[1]; j <= arr[2]; j++) { dp[i][(int) arr[i]] += dp[i - 1][j] * (i - 1) * (i - 2) / 2; } } else if (arr[i] == arr[2]) { dp[i][(int) arr[i]] = dp[i - 1][(int) arr[i]] * (i - 1) * (i - 2) / 6; for (int j = (int) arr[2]; j < N; j++) { dp[i][j] += dp[i - 1][j]; } } else { for (int j = (int) arr[2]; j < N; j++) { dp[i][j] += dp[i - 1][j]; } } } // Calculate the final answer by summing the dp values for elements between arr[0] and arr[2] long ans = 0; for (int j = (int) arr[0]; j <= arr[2]; j++) { ans += dp[n - 1][j]; } return ans; } public static void main(String[] args) { long[] arr = { 1, 3, 3, 4 }; int n = arr.length; System.out.println(noOfTriples(arr, n)); }} |
Python3
def no_of_triples(arr, n): N = 1005 # Define the value of N # Sorting the array arr.sort() # Initializing a 2D DP array with zeros dp = [[0 for _ in range(N)] for _ in range(n)] dp[0][arr[0]] = 1 for i in range(1, n): dp[i][arr[i]] = 1 # Filling in the DP array for values between arr[i-1] and arr[i] for j in range(arr[i - 1] + 1, arr[i]): dp[i][j] = dp[i - 1][j] if arr[i] == arr[1]: # Handling special case when arr[i] equals arr[1] for j in range(arr[1], arr[2] + 1): dp[i][arr[i]] += dp[i - 1][j] * (i - 1) * (i - 2) // 2 elif arr[i] == arr[2]: # Handling special case when arr[i] equals arr[2] dp[i][arr[i]] = dp[i - 1][arr[i]] * (i - 1) * (i - 2) // 6 for j in range(arr[2], N): dp[i][j] += dp[i - 1][j] else: # Filling in the DP array for values greater than arr[2] for j in range(arr[2], N): dp[i][j] += dp[i - 1][j] ans = 0 # Summing up the values in the last row for indices between arr[0] and arr[2] for j in range(arr[0], arr[2] + 1): ans += dp[n - 1][j] return ansif __name__ == "__main__": arr = [1, 3, 3, 4] n = len(arr) print(no_of_triples(arr, n))# This code is contributed by rambabuguphka |
C#
using System;public class GFG{ const int N = 1005; static long[,] dp = new long[N, N]; // Function to count the number of triples in the array static long noOfTriples(long[] arr, int n) { // Sort the array in non-decreasing order Array.Sort(arr); // Initialize the dp array to store intermediate results Array.Clear(dp, 0, dp.Length); dp[0, (int)arr[0]] = 1; // Iterate through the array elements for (int i = 1; i < n; i++) { // Update dp for the current element dp[i, (int)arr[i]] = 1; // Fill the dp array for values between the previous element and the current element for (int j = (int)arr[i - 1] + 1; j < arr[i]; j++) { dp[i, j] = dp[i - 1, j]; } // Handle special cases when the current element is equal to arr[1] or arr[2] if (arr[i] == arr[1]) { for (int j = (int)arr[1]; j <= arr[2]; j++) { dp[i, (int)arr[i]] += dp[i - 1, j] * (i - 1) * (i - 2) / 2; } } else if (arr[i] == arr[2]) { dp[i, (int)arr[i]] = dp[i - 1, (int)arr[i]] * (i - 1) * (i - 2) / 6; for (int j = (int)arr[2]; j < N; j++) { dp[i, j] += dp[i - 1, j]; } } else { for (int j = (int)arr[2]; j < N; j++) { dp[i, j] += dp[i - 1, j]; } } } // Calculate the final answer by summing the dp values for elements between arr[0] and arr[2] long ans = 0; for (int j = (int)arr[0]; j <= arr[2]; j++) { ans += dp[n - 1, j]; } return ans; } public static void Main(string[] args) { long[] arr = { 1, 3, 3, 4 }; int n = arr.Length; Console.WriteLine(noOfTriples(arr, n)); }} |
Javascript
function noOfTriples(arr) { const N = 1005; const dp = new Array(N).fill(null).map(() => new Array(N).fill(0)); // Sort the array in non-decreasing order arr.sort((a, b) => a - b); dp[0][arr[0]] = 1; const n = arr.length; for (let i = 1; i < n; i++) { // Update dp for the current element dp[i][arr[i]] = 1; // Fill the dp array for values between the previous element and the current element for (let j = arr[i - 1] + 1; j < arr[i]; j++) { dp[i][j] = dp[i - 1][j]; } // Handle special cases when the current element is equal to arr[1] or arr[2] if (arr[i] === arr[1]) { for (let j = arr[1]; j <= arr[2]; j++) { dp[i][arr[i]] += (dp[i - 1][j] * (i - 1) * (i - 2)) / 2; } } else if (arr[i] === arr[2]) { dp[i][arr[i]] = (dp[i - 1][arr[i]] * (i - 1) * (i - 2)) / 6; for (let j = arr[2]; j < N; j++) { dp[i][j] += dp[i - 1][j]; } } else { for (let j = arr[2]; j < N; j++) { dp[i][j] += dp[i - 1][j]; } } } // Calculate the final answer by summing the dp values for elements between arr[0] and arr[2] let ans = 0; for (let j = arr[0]; j <= arr[2]; j++) { ans += dp[n - 1][j]; } return ans;}const arr = [1, 3, 3, 4];console.log(noOfTriples(arr)); |
Output
1
Time Complexity: O(n Log n)
Auxiliary Space: O(1)
If you like neveropen and would like to contribute, you can also write an article using write.geeksforgeeks.org or mail your article to review-team@geeksforgeeks.org. See your article appearing on the neveropen main page and help other Geeks.
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
