Contar formas de formar trillizos de productos mínimos

Dada una array de enteros positivos. Necesitamos encontrar cuántos triples de índices (i, j, k) (i < j < k), tales que a[i] * a[j] * a[k] es el mínimo posible.

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).

Los siguientes casos surgen en este problema.  

1. Los tres elementos mínimos son iguales. Por ejemplo {1, 1, 1, 1, 2, 3, 4}. La solución para tales casos es ⁿ C ₃ .
2. Dos elementos son iguales. Por ejemplo {1, 2, 2, 2, 3} o {1, 1, 2, 2}. En este caso, el recuento de ocurrencias del primero (o elemento mínimo) no puede ser más de 2. Si el elemento mínimo aparece dos veces, entonces la respuesta es el recuento del segundo elemento (Podemos elegir solo 1 de todas las ocurrencias del segundo elemento. Si el mínimo elemento aparece una vez, la cuenta es ⁿ C ₂ .
3. Los tres elementos son distintos. Por ejemplo {1, 2, 3, 3, 5}. En este caso, la respuesta es el conteo de ocurrencias del tercer elemento (o ⁿ C ₁ ).

Primero ordenamos la array en orden creciente. Luego cuente la frecuencia de 3 elementos del 3er elemento desde el inicio. Deje que la frecuencia sea ‘contar’. Surgen los siguientes casos.  

• Si el tercer elemento es igual al primer elemento, no. de triples será (cuenta-2)*(cuenta-1)*(cuenta)/6, donde cuenta es la frecuencia del 3er elemento.
• Si el tercer elemento es igual al segundo elemento, no. de triples será (cuenta-1)*(cuenta)/2. De otra manera no. de triples será valor de cuenta.

Implementación:

// 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 triples
long 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 code
int main()
{
    long long arr[] = { 1, 3, 3, 4 };
    int n = sizeof(arr) / sizeof(arr[0]);
    cout << noOfTriples(arr, n);
    return 0;
}

// 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 program to count number
# of ways we can form triplets
# with minimum product.
 
# function to calculate number of triples
def 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 code
arr = [1, 3, 3, 4]
n = len(arr)
print (noOfTriples(arr, n))
 
# This code is contributed by "Abhishek Sharma 44"

// C# program to count number of ways
// we can form triplets with minimum product.
using System;
 
class GFG {
     
// function to calculate number of triples
static 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 code
public 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.

<?php
// PHP 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
    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.
?>

<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>

1

Complejidad de Tiempo: O(n Log n) 
Espacio Auxiliar: O(1)

La solución se puede optimizar encontrando primero el elemento mínimo y su frecuencia y, si la frecuencia es menor que 3, luego encontrando el segundo mínimo y su frecuencia. Si la frecuencia general es menor que 3, entonces encuentre el tercer mínimo y su frecuencia. La complejidad temporal de esta solución optimizada sería O(n)

Este artículo es una contribución de Sagar Shukla . Si te gusta GeeksforGeeks y te gustaría contribuir, también puedes escribir un artículo usando write.geeksforgeeks.org o enviar tu artículo por correo a review-team@geeksforgeeks.org. Vea su artículo que aparece en la página principal de GeeksforGeeks y ayude a otros Geeks.