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 3 )
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++
// 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
// 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
# 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#
// 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
Javascript
<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 2 ), ya que estamos usando bucles anidados para atravesar N*N veces.
Espacio auxiliar: O(1), ya que no estamos utilizando ningún espacio adicional.
Publicación traducida automáticamente
Artículo escrito por chitrasingla2001 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA