Dados N números y dos números L y R, la tarea es imprimir el conteo de números en el rango [L, R] que son divisibles por todos los elementos de la array.
Ejemplos:
Entrada: a[] = {1, 4, 2], L = 1, R = 10
Salida: 2
En el rango [1, 10], los números 4 y 8 son divisibles por todos los elementos de la array.
Entrada: a[] = {1, 3, 2], L = 7, R = 11
Salida: 0
Un enfoque ingenuo es iterar de L a R y contar los números que son divisibles por todos los elementos de la array.
Complejidad de tiempo: O ((RL) * N), ya que usaremos bucles anidados, un bucle externo para iterar de L a R y un bucle interno para atravesar los elementos de la array.
Espacio auxiliar: O(1), ya que no usaremos ningún espacio adicional.
Un enfoque eficiente es encontrar el MCM de N números y luego contar los números que son divisibles por MCM en el rango [L, R]. Los números divisibles por LCM hasta R son R/LCM. Entonces, usando el principio de exclusión, el conteo será (R / LCM) – ((L – 1) / LCM).
A continuación se muestra la implementación del enfoque anterior.
C++
// C++ program to count numbers in a range
// that are divisible by all array elements
#include <bits/stdc++.h>
using namespace std;
// Function to find the lcm of array
int findLCM(int arr[], int n)
{
int lcm = arr[0];
// Iterate in the array
for (int i = 1; i < n; i++) {
// Find lcm
lcm = (lcm * arr[i]) / __gcd(arr[i], lcm);
}
return lcm;
}
// Function to return the count of numbers
int countNumbers(int arr[], int n, int l, int r)
{
// Function call to find the
// LCM of N numbers
int lcm = findLCM(arr, n);
// Return the count of numbers
int count = (r / lcm) - ((l - 1) / lcm);
}
// Driver Code
int main()
{
int arr[] = { 1, 4, 2 };
int n = sizeof(arr) / sizeof(arr[0]);
int l = 1, r = 10;
cout << countNumbers(arr, n, l, r);
return 0;
}
Java
// Java program to count numbers in a range
// that are divisible by all array elements
class GFG
{
// Function to calculate gcd
static int __gcd(int a, int b)
{
// Everything divides 0
if (a == 0 || b == 0)
return 0;
// 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 find the lcm of array
static int findLCM(int arr[], int n)
{
int lcm = arr[0];
// Iterate in the array
for (int i = 1; i < n; i++)
{
// Find lcm
lcm = (lcm * arr[i]) / __gcd(arr[i], lcm);
}
return lcm;
}
// Function to return the count of numbers
static int countNumbers(int arr[], int n,
int l, int r)
{
// Function call to find the
// LCM of N numbers
int lcm = findLCM(arr, n);
// Return the count of numbers
int count = (r / lcm) - ((l - 1) / lcm);
return count;
}
// Driver Code
public static void main(String args[])
{
int arr[] = { 1, 4, 2 };
int n = arr.length;
int l = 1, r = 10;
System.out.println(countNumbers(arr, n, l, r));
}
}
// This code is contributed by Mukul Singh
Python3
# Python program to count numbers in # a range that are divisible by all # array elements import math # Function to find the lcm of array def findLCM(arr, n): lcm = arr[0] # Iterate in the array for i in range(1, n - 1): # Find lcm lcm = (lcm * arr[i]) / math.gcd(arr[i], lcm) return lcm # Function to return the count of numbers def countNumbers(arr, n, l, r): # Function call to find the # LCM of N numbers lcm = int(findLCM(arr, n)) # Return the count of numbers count = (r / lcm) - ((l - 1) / lcm) print(int(count)) # Driver Code arr = [1, 4, 2] n = len(arr) l = 1 r = 10 countNumbers(arr, n, l, r) # This code is contributed # by Shivi_Aggarwal
C#
// C# program to count numbers in a range
// that are divisible by all array elements
using System;
class GFG
{
// Function to calculate gcd
static int __gcd(int a, int b)
{
// Everything divides 0
if (a == 0 || b == 0)
return 0;
// 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 find the lcm of array
static int findLCM(int []arr, int n)
{
int lcm = arr[0];
// Iterate in the array
for (int i = 1; i < n; i++)
{
// Find lcm
lcm = (lcm * arr[i]) / __gcd(arr[i], lcm);
}
return lcm;
}
// Function to return the count of numbers
static int countNumbers(int []arr, int n,
int l, int r)
{
// Function call to find the
// LCM of N numbers
int lcm = findLCM(arr, n);
// Return the count of numbers
int count = (r / lcm) - ((l - 1) / lcm);
return count;
}
// Driver Code
public static void Main()
{
int []arr = { 1, 4, 2 };
int n = arr.Length;
int l = 1, r = 10;
Console.WriteLine(countNumbers(arr, n, l, r));
}
}
// This code is contributed by Ryuga
PHP
<?php
// PHP program to count numbers in a range
// that are divisible by all array elements
// Function to calculate gcd
function __gcd($a, $b)
{
// Everything divides 0
if ($a == 0 || $b == 0)
return 0;
// 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 find the lcm of array
function findLCM($arr, $n)
{
$lcm = $arr[0];
// Iterate in the array
for ($i = 1; $i < $n; $i++)
{
// Find lcm
$lcm = ($lcm * $arr[$i]) /
__gcd($arr[$i], $lcm);
}
return $lcm;
}
// Function to return the count of numbers
function countNumbers($arr, $n, $l, $r)
{
// Function call to find the
// LCM of N numbers
$lcm = findLCM($arr, $n);
// Return the count of numbers
$count = (int)($r / $lcm) -
(int)(($l - 1) / $lcm);
return $count;
}
// Driver Code
$arr = array(1, 4, 2);
$n = sizeof($arr);
$l = 1; $r = 10;
echo countNumbers($arr, $n, $l, $r);
// This code is contributed
// by Akanksha Rai
?>
Javascript
<script>
// Javascript program to count numbers in a range
// that are divisible by all array elements
// Function to calculate gcd
function __gcd(a , b) {
// Everything divides 0
if (a == 0 || b == 0)
return 0;
// 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 find the lcm of array
function findLCM(arr , n) {
var lcm = arr[0];
// Iterate in the array
for (i = 1; i < n; i++) {
// Find lcm
lcm = parseInt((lcm * arr[i]) / __gcd(arr[i], lcm));
}
return lcm;
}
// Function to return the count of numbers
function countNumbers(arr , n , l , r) {
// Function call to find the
// LCM of N numbers
var lcm = findLCM(arr, n);
// Return the count of numbers
var count = parseInt((r / lcm) - ((l - 1) / lcm));
return count;
}
// Driver Code
var arr = [ 1, 4, 2 ];
var n = arr.length;
var l = 1, r = 10;
document.write(countNumbers(arr, n, l, r));
// This code contributed by umadevi9616
</script>
Producción:
2
Complejidad de tiempo: O (N * log (elemento máximo de la array)), ya que estamos usando un ciclo para atravesar N veces y la función gcd para encontrar el lcm en cada recorrido.
Espacio auxiliar: O(1), ya que no estamos utilizando ningún espacio adicional.