Find numbers in between [L, R] which are divisible by all Array elements

0 0 7 minutes read

Given an array arr[] containing N positive integers and two variables L and R indicating a range of integers from L to R (inclusive). The task is to print all the numbers between L to R which are divisible by all array elements. If no such value exists print -1.

Input: arr[] = {3, 5, 12}, L = 90, R = 280
Output: 120 180 240
Explanation: 120, 180, 240 are the numbers which are divisible by all the arr[] elements.

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

Naive Approach: In this approach for every element in range [L, R] check if it is divisible by all the elements of the array.

Time Complexity: O((R-L)*N)
Auxiliary Space: O(1)

Efficient Approach: The given problem can be solved using basic math. Any element divisible by all the elements of the array is a multiple of the LCM of all the array elements. Find the multiples of LCM in the range [L, R] and store in an array. At last print the numbers stored in the array.

Time Complexity: O(N)
Auxiliary Space: O(R – L)

Space Optimized Approach: Below steps can be used to solve the problem:

Calculate the LCM of all the elements of given arr[]
Now, check the LCM for these conditions:
1. If (LCM < L and LCM*2 > R), then print -1.
2. If (LCM > R), then print -1.
Now, take the nearest value of L (between L to R) which is divisible by the LCM, say i.
Now, start printing i and increment it by LCM every time after printing, until it becomes greater than R.

Below is the implementation of the above approach:

C++

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

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

Python3

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

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

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

Output

120 180 240

Time Complexity: O(N)
Auxiliary Space: O(1)

Recommended

Solve DSA problems on GfG Practice.

Solve Problems

Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 zambiatek!