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:
- If (LCM < L and LCM*2 > R), then print -1.
- 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 existsvoid 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 Codeint 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 approachimport java.util.*;class GFG{// Recursive function to return gcd of a and bstatic 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 existsstatic 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 Codepublic 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 bdef __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 existsdef 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 Codeif __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 approachusing 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)
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 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
