Recuento de tripletes (a, b, c) en el Array tal que a divide a b y b divide a c

Dado un arreglo arr[] de enteros positivos de tamaño N , la tarea es contar el número de tripletes en el arreglo tal que a[i] divide a[j] y a[j] divide a[k] e i < j < k.
Ejemplos:
 

Entrada: arr[] = {1, 2, 3, 4, 5, 6} 
Salida: 3 
Explicación: 
Los tripletes son: (1, 2, 4), (1, 2, 6), (1, 3, 6 ).
Entrada: arr[] = {1, 2, 2} 
Salida: 1 
Explicación: 
El triplete es (1, 2, 2) 
 

Enfoque ingenuo: para resolver el problema mencionado anteriormente, intentaremos implementar una solución de fuerza bruta . Recorra la array para los tres números a[i], a[j] y a[k] y cuente el número de tripletes que satisfacen la condición dada.
Complejidad de tiempo: O(N ³ ) 
Complejidad de espacio auxiliar: O(1)
Enfoque eficiente: Para optimizar el método anterior, podemos atravesar la array para el elemento central desde el índice 1 hasta n-2 y para cada elemento central podemos atravesar la izquierda array para a[i] y cuente el número de posibles a[i] tal que a[i] divide a[j]. De manera similar, podemos atravesar el arreglo correcto y hacer lo mismo para a[k].
A continuación se muestra la implementación del enfoque anterior: 
 

// C++ program to find count of triplets
// (a, b, c) in the Array such that
// a divides b and b divides c
 
#include <bits/stdc++.h>
using namespace std;
 
// Function to count triplets
int getCount(int arr[], int n)
{
    int count = 0;
 
    // Iterate for middle element
    for (int j = 1; j < n - 1; j++) {
        int p = 0, q = 0;
 
        // Iterate left array for a[i]
        for (int i = 0; i < j; i++) {
 
            if (arr[j] % arr[i] == 0)
                p++;
        }
 
        // Iterate right array for a[k]
        for (int k = j + 1; k < n; k++) {
 
            if (arr[k] % arr[j] == 0)
                q++;
        }
 
        count += p * q;
    }
    // return the final result
    return count;
}
 
// Driver code
int main()
{
    int arr[] = { 1, 2, 2 };
    int N = sizeof(arr) / sizeof(arr[0]);
 
    cout << getCount(arr, N) << endl;
 
    return 0;
}

// Java program to find count of triplets
// (a, b, c) in the Array such that
// a divides b and b divides c
import java.io.*;
import java.util.*;
 
class GFG {
     
// Function to count triplets
static int getCount(int arr[], int n)
{
    int count = 0;
 
    // Iterate for middle element
    for(int j = 1; j < n - 1; j++)
    {
       int p = 0, q = 0;
        
       // Iterate left array for a[i]
       for(int i = 0; i < j; i++)
       {
          if (arr[j] % arr[i] == 0)
              p++;
       }
        
       // Iterate right array for a[k]
       for(int k = j + 1; k < n; k++)
       {
          if (arr[k] % arr[j] == 0)
              q++;
       }
        
       count += p * q;
    }
     
    // return the final result
    return count;
}
 
// Driver code
public static void main(String[] args)
{
    int arr[] = { 1, 2, 2 };
    int N = arr.length;
     
    System.out.println(getCount(arr, N));
}
}
 
// This code is contributed by coder001

# Python3 program to find the count of
# triplets (a, b, c) in the Array such
# that a divides b and b divides c
 
# Function to count triplets
def getCount(arr, n):
    count = 0
 
    # Iterate for middle element
    for j in range(1, n - 1):
        p, q = 0, 0
 
        # Iterate left array for a[i]
        for i in range(j):
 
            if (arr[j] % arr[i] == 0):
                p += 1
 
        # Iterate right array for a[k]
        for k in range(j + 1, n):
 
            if (arr[k] % arr[j] == 0):
                q += 1
 
        count += p * q
         
    # Return the final result
    return count
 
# Driver code
if __name__ == '__main__':
     
    arr = [ 1, 2, 2 ]
    N = len(arr)
     
    print(getCount(arr, N))
     
# This code is contributed by mohit kumar 29   

// C# program to find count of triplets
// (a, b, c) in the Array such that
// a divides b and b divides c
using System;
 
class GFG{
 
// Function to count triplets
public static int getCount(int[] arr, int n)
{
    int count = 0;
 
    // Iterate for middle element
    for(int j = 1; j < n - 1; j++)
    {
        int p = 0, q = 0;
 
        // Iterate left array for a[i]
        for(int i = 0; i < j; i++)
        {
            if (arr[j] % arr[i] == 0)
                p++;
        }
 
        // Iterate right array for a[k]
        for(int k = j + 1; k < n; k++)
        {
            if (arr[k] % arr[j] == 0)
                q++;
        }
        count += p * q;
    }
 
    // return the final result
    return count;
}
 
// Driver code
public static void Main()
{
    int[] arr = { 1, 2, 2 };
    int N = arr.Length;
 
    Console.WriteLine(getCount(arr, N));
}
}
 
// This code is contributed by jrishabh99

<script>
 
// Javascript program to find count of triplets
// (a, b, c) in the Array such that
// a divides b and b divides c
 
// Function to count triplets
function getCount(arr, n)
{
    var count = 0;
 
    // Iterate for middle element
    for(var j = 1; j < n - 1; j++)
    {
       var p = 0, q = 0;
        
       // Iterate left array for a[i]
       for(var i = 0; i < j; i++)
       {
          if (arr[j] % arr[i] == 0)
              p++;
       }
        
       // Iterate right array for a[k]
       for(var k = j + 1; k < n; k++)
       {
          if (arr[k] % arr[j] == 0)
              q++;
       }
        
       count += p * q;
    }
     
    // return the final result
    return count;
}
 
// Driver Code
var arr = [ 1, 2, 2 ];
var N = arr.length;
 
document.write(getCount(arr, N));
 
// This code is contributed by Khushboogoyal499
     
</script>

1

Complejidad de tiempo: O(N ² ), ya que estamos usando bucles anidados para atravesar N*N veces.
Espacio auxiliar: O(1), ya que no estamos utilizando ningún espacio adicional.