Conteo de elementos en un Array dado divisible por todos los elementos en su prefijo

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 ₁ , X ₂ , X ₃ , X ₄ , . . ., X _n } , si X se divide por MCM de {X ₁ , X ₂ , X ₃ , X ₄ , …, 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:

1. Cree una variable ans que almacene la respuesta final e inicialícela con 0.
2. 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] .
3. 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.
4. Imprima ans como la respuesta final a este problema.

A continuación se muestra la implementación del enfoque anterior:

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

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

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