Encuentre números entre [L, R] que sean divisibles por todos los elementos de Array

Dada una array arr[] que contiene N enteros positivos y dos variables L y R que indican un rango de enteros de L a R (inclusive). La tarea es imprimir todos los números entre L y R que son divisibles por todos los elementos de la array. Si no existe tal valor, imprima -1.

Entrada: arr[] = {3, 5, 12}, L = 90, R = 280
Salida: 120 180 240 
Explicación: 120, 180, 240 son los números que son divisibles por todos los elementos arr[].

Entrada: arr[] = {4, 7, 13, 16}, L = 200, R = 600
Salida: -1

Enfoque ingenuo: en este enfoque, para cada elemento en el rango [L, R], verifique si es divisible por todos los elementos de la array.

Complejidad de Tiempo: O((RL)*N)
Espacio Auxiliar: O(1)

Enfoque eficiente: el problema dado se puede resolver usando matemáticas básicas. Cualquier elemento divisible por todos los elementos del arreglo es un múltiplo del MCM de todos los elementos del arreglo. Encuentre los múltiplos de LCM en el rango [L, R] y guárdelos en una array. Por fin imprima los números almacenados en la array.

Complejidad temporal: O(N)
Espacio auxiliar: O(R – L)

Enfoque de espacio optimizado: los pasos a continuación se pueden utilizar para resolver el problema:

1. Calcule el MCM de todos los elementos de arr[] dado
2. Ahora, verifique el LCM para estas condiciones:
   1. Si (LCM < L y LCM*2 > R) , imprima -1.
   2. Si (LCM > R) , imprima -1.
3. Ahora, tome el valor más cercano de L (entre L y R ) que sea divisible por el LCM , digamos i .
4. Ahora, comience a imprimir i e increméntelo en LCM cada vez que imprima, hasta que sea mayor que R.

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

// C++ program for the above approach
#include <bits/stdc++.h>
using namespace std;
 
// Function to return Kth smallest
// prime number if it exists
void solve(int* arr, int N, int L, int R)
{
    // For storing the LCM
    int LCM = arr[0];
 
    // Loop to iterate the array
    for (int i = 1; i < N; i++) {
        // Taking LCM of numbers
        LCM = (LCM * arr[i]) /
            (__gcd(LCM, arr[i]));
    }
 
    // Checking if no elements is divisible
    // by all elements of given array of given
    // range, print -1
    if ((LCM < L && LCM * 2 > R) || LCM > R) {
        cout << "-1";
        return;
    }
 
    // Taking nearest value of L which is
    // divisible by whole array
    int k = (L / LCM) * LCM;
 
    // If k is less than L, make it in the
    // range between L to R
    if (k < L)
        k = k + LCM;
 
    // Loop to iterate the from L to R
    // and printing the numbers which
    // are divisible by all array elements
    for (int i = k; i <= R; i = i + LCM) {
        cout << i << ' ';
    }
}
 
// Driver Code
int main()
{
    int L = 90;
    int R = 280;
    int arr[] = { 3, 5, 12 };
    int N = sizeof(arr) / sizeof(arr[0]);
    solve(arr, N, L, R);
    return 0;
}

// Java program for the above approach
import java.util.*;
 
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 Kth smallest
// prime number if it exists
static void solve(int[] arr, int N, int L, int R)
{
     
    // For storing the LCM
    int LCM = arr[0];
 
    // Loop to iterate the array
    for(int i = 1; i < N; i++)
    {
         
        // Taking LCM of numbers
        LCM = (LCM * arr[i]) /
        (__gcd(LCM, arr[i]));
    }
 
    // Checking if no elements is divisible
    // by all elements of given array of given
    // range, print -1
    if ((LCM < L && LCM * 2 > R) || LCM > R)
    {
        System.out.println("-1");
        return;
    }
 
    // Taking nearest value of L which is
    // divisible by whole array
    int k = (L / LCM) * LCM;
 
    // If k is less than L, make it in the
    // range between L to R
    if (k < L)
        k = k + LCM;
 
    // Loop to iterate the from L to R
    // and printing the numbers which
    // are divisible by all array elements
    for(int i = k; i <= R; i = i + LCM)
    {
        System.out.print(i + " ");
    }
}
 
// Driver Code
public static void main(String args[])
{
    int L = 90;
    int R = 280;
    int arr[] = { 3, 5, 12 };
    int N = arr.length;
     
    solve(arr, N, L, R);
}
}
 
// This code is contributed by sanjoy_62

# Python program 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 Kth smallest
# prime number if it exists
def solve(arr, N, L, R):
   
    # For storing the LCM
    LCM = arr[0];
 
    # Loop to iterate the array
    for i in range(1, N):
       
        # Taking LCM of numbers
        LCM = (LCM * arr[i]) // (__gcd(LCM, arr[i]));
 
    # Checking if no elements is divisible
    # by all elements of given array of given
    # range, pr-1
    if ((LCM < L and LCM * 2 > R) or LCM > R):
        print("-1");
        return;
 
    # Taking nearest value of L which is
    # divisible by whole array
    k = (L // LCM) * LCM;
 
    # If k is less than L, make it in the
    # range between L to R
    if (k < L):
        k = k + LCM;
 
    # Loop to iterate the from L to R
    # and printing the numbers which
    # are divisible by all array elements
    for i in range(k,R+1,LCM):
        print(i, end=" ");
 
# Driver Code
if __name__ == '__main__':
    L = 90;
    R = 280;
    arr = [3, 5, 12];
    N = len(arr);
 
    solve(arr, N, L, R);
 
# This code is contributed by 29AjayKumar

// 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 Kth smallest
  // prime number if it exists
  static void solve(int[] arr, int N, int L, int R)
  {
 
    // For storing the LCM
    int LCM = arr[0];
 
    // Loop to iterate the array
    for(int i = 1; i < N; i++)
    {
 
      // Taking LCM of numbers
      LCM = (LCM * arr[i]) /
        (__gcd(LCM, arr[i]));
    }
 
    // Checking if no elements is divisible
    // by all elements of given array of given
    // range, print -1
    if ((LCM < L && LCM * 2 > R) || LCM > R)
    {
      Console.WriteLine("-1");
      return;
    }
 
    // Taking nearest value of L which is
    // divisible by whole array
    int k = (L / LCM) * LCM;
 
    // If k is less than L, make it in the
    // range between L to R
    if (k < L)
      k = k + LCM;
 
    // Loop to iterate the from L to R
    // and printing the numbers which
    // are divisible by all array elements
    for(int i = k; i <= R; i = i + LCM)
    {
      Console.Write(i + " ");
    }
  }
 
  // Driver Code
  public static void Main(String []args)
  {
    int L = 90;
    int R = 280;
    int []arr = { 3, 5, 12 };
    int N = arr.Length;
 
    solve(arr, N, L, R);
  }
}
 
// This code is contributed by 29AjayKumar

  <script>
      // JavaScript code for the above approach
      // Recursive function to return gcd of a and b
      function __gcd(a, b) {
 
          // Everything divides 0
          if (b == 0) {
              return a;
          }
 
          return __gcd(b, a % b);
      }
       
      // Function to return Kth smallest
      // prime number if it exists
      function solve(arr, N, L, R)
      {
       
          // For storing the LCM
          let LCM = arr[0];
 
          // Loop to iterate the array
          for (let i = 1; i < N; i++)
          {
           
              // Taking LCM of numbers
              LCM = Math.floor((LCM * arr[i]) /
                  (__gcd(LCM, arr[i])));
          }
 
          // Checking if no elements is divisible
          // by all elements of given array of given
          // range, print -1
          if ((LCM < L && LCM * 2 > R) || LCM > R) {
              document.write("-1");
              return;
          }
 
          // Taking nearest value of L which is
          // divisible by whole array
          let k = Math.floor((L / LCM)) * LCM;
 
          // If k is less than L, make it in the
          // range between L to R
          if (k < L)
              k = k + LCM;
 
          // Loop to iterate the from L to R
          // and printing the numbers which
          // are divisible by all array elements
          for (let i = k; i <= R; i = i + LCM) {
              document.write(i + " ");
          }
      }
 
      // Driver Code
      let L = 90;
      let R = 280;
      let arr = [3, 5, 12];
      let N = arr.length;
      solve(arr, N, L, R);
 
// This code is contributed by Potta Lokesh
  </script>

120 180 240 

Complejidad temporal: O(N)
Espacio auxiliar: O(1)