Dada una array arr[] que contiene N enteros positivos, la tarea es encontrar el número total de elementos en la array que son divisibles por todos los elementos presentes antes de ellos.
Ejemplos:
Entrada: arr[] = {10, 6, 60, 120, 30, 360}
Salida: 3
Explicación: 60, 120 y 360 son los elementos necesarios.Entrada: arr[] = {2, 6, 5, 60}
Salida: 2
Explicación: 6 y 60 son los elementos.
Planteamiento: Como se sabe, que cualquier número X se divide por {X 1 , X 2 , X 3 , X 4 , . . ., X n } , si X se divide por MCM de {X 1 , X 2 , X 3 , X 4 , …, X n ). Y MCM de cualquier número A , B es [(A*B)/mcd(A, B)] . Ahora, para resolver este problema, siga los pasos a continuación:
- Cree una variable ans que almacene la respuesta final e inicialícela con 0.
- Cree otra variable lcm que almacene LCM hasta el i -ésimo elemento mientras itera a través de la array. Inicialice lcm con arr[0] .
- Itere sobre la array de i = 1 a i = N y, en cada iteración, verifique si arr[i] está dividido por lcm. En caso afirmativo, incremente ans en 1. Además, actualice lcm con lcm hasta el i -ésimo elemento.
- Imprima ans como la respuesta final a este problema.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ code to implement the above approach #include <bits/stdc++.h> using namespace std; // Function to return total number of // elements which are divisible by // all their previous elements int countElements(int arr[], int N) { int ans = 0; int lcm = arr[0]; for (int i = 1; i < N; i++) { // To check if number is divisible // by lcm of all previous elements if (arr[i] % lcm == 0) { ans++; } // Updating LCM lcm = (lcm * arr[i]) / __gcd(lcm, arr[i]); } return ans; } // Driver code int main() { int arr[] = { 10, 6, 60, 120, 30, 360 }; int N = sizeof(arr) / sizeof(int); cout << countElements(arr, N); return 0; }
Java
// Java program for the above approach import java.util.*; public class GFG { // Recursive function to return gcd of a and b static int __gcd(int a, int b) { // Everything divides 0 if (a == 0) return b; if (b == 0) return a; // base case if (a == b) return a; // a is greater if (a > b) return __gcd(a - b, b); return __gcd(a, b - a); } // Function to return total number of // elements which are divisible by // all their previous elements static int countElements(int arr[], int N) { int ans = 0; int lcm = arr[0]; for (int i = 1; i < N; i++) { // To check if number is divisible // by lcm of all previous elements if (arr[i] % lcm == 0) { ans++; } // Updating LCM lcm = (lcm * arr[i]) / __gcd(lcm, arr[i]); } return ans; } public static void main(String args[]) { int arr[] = { 10, 6, 60, 120, 30, 360 }; int N = arr.length; System.out.print(countElements(arr, N)); } } // This code is contributed by Samim Hossain Mondal.
Python3
# Python code for the above approach # Recursive function to return gcd of a and b def __gcd(a, b): # Everything divides 0 if (a == 0): return b; if (b == 0): return a; # base case if (a == b): return a; # a is greater if (a > b): return __gcd(a - b, b); return __gcd(a, b - a); # Function to return total number of # elements which are divisible by # all their previous elements def countElements(arr, N): ans = 0; lcm = arr[0]; for i in range(1, N): # To check if number is divisible # by lcm of all previous elements if (arr[i] % lcm == 0): ans += 1 # Updating LCM lcm = (lcm * arr[i]) / __gcd(lcm, arr[i]); return ans; # Driver code arr = [10, 6, 60, 120, 30, 360]; N = len(arr) print(countElements(arr, N)); # This code is contributed by Saurabh Jaiswal
C#
// C#program for the above approach using System; public class GFG { // Recursive function to return gcd of a and b static int __gcd(int a, int b) { // Everything divides 0 if (a == 0) return b; if (b == 0) return a; // base case if (a == b) return a; // a is greater if (a > b) return __gcd(a - b, b); return __gcd(a, b - a); } // Function to return total number of // elements which are divisible by // all their previous elements static int countElements(int[] arr, int N) { int ans = 0; int lcm = arr[0]; for (int i = 1; i < N; i++) { // To check if number is divisible // by lcm of all previous elements if (arr[i] % lcm == 0) { ans++; } // Updating LCM lcm = (lcm * arr[i]) / __gcd(lcm, arr[i]); } return ans; } public static void Main() { int[] arr = { 10, 6, 60, 120, 30, 360 }; int N = arr.Length; Console.Write(countElements(arr, N)); } } // This code is contributed by ukasp.
Javascript
<script> // JavaScript code for the above approach // Recursive function to return gcd of a and b function __gcd(a, b) { // Everything divides 0 if (a == 0) return b; if (b == 0) return a; // base case if (a == b) return a; // a is greater if (a > b) return __gcd(a - b, b); return __gcd(a, b - a); } // Function to return total number of // elements which are divisible by // all their previous elements function countElements(arr, N) { let ans = 0; let lcm = arr[0]; for (let i = 1; i < N; i++) { // To check if number is divisible // by lcm of all previous elements if (arr[i] % lcm == 0) { ans++; } // Updating LCM lcm = (lcm * arr[i]) / __gcd(lcm, arr[i]); } return ans; } // Driver code let arr = [10, 6, 60, 120, 30, 360]; let N = arr.length document.write(countElements(arr, N)); // This code is contributed by Potta Lokesh </script>
3
Complejidad de tiempo: O(N * logD) donde D es el elemento de array máximo
Espacio auxiliar: O(N)
Publicación traducida automáticamente
Artículo escrito por saurabh15899 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA