N-th multiple in sorted list of multiples of two numbers
Given three positive integers a, b and n. Consider a list that has all multiples of ‘a’ and ‘b’. the list is sorted and duplicates are removed. The task is to find n-th element of the list.
Examples :
Input : a = 3, b = 5, n = 5 Output : 10 a = 3 b = 5, Multiple of 3 are 3, 6, 9, 12, 15,... and multiples of 5 are 5, 10, 15, 20,.... After deleting duplicate element and sorting: 3, 5, 6, 9, 10, 12, 15, 18, 20,.... The 5th element in the sequence is 10. Input : n = 6, a = 2, b = 3 Output : 9
Method 1: (Brute Force)
Generate the first ‘n’ multiple of ‘a’. Now, generate first ‘n’ multiple of b such that it do not belong to the first n multiple of ‘a’. This can be done using Binary Search.
C++
// C++ program to find n-th number in the sorted // list of multiples of two numbers. #include<bits/stdc++.h> using namespace std; // Return the n-th number in the sorted // list of multiples of two numbers. int nthElement( int a, int b, int n) { vector< int > seq; // Generating first n multiple of a. for ( int i = 1; i <= n; i++) seq.push_back(a*i); // Sorting the sequence. sort(seq.begin(), seq.end()); // Generating and storing first n multiple of b // and storing if not present in the sequence. for ( int i = 1, k = n; i <= n && k; i++) { // If not present in the sequence if (!binary_search(seq.begin(), seq.end(), b*i)) { // Storing in the sequence. seq.push_back(b*i); sort(seq.begin(), seq.end()); k--; } } return seq[n - 1]; } // Driven Program int main() { int a = 3, b = 5, n = 5; cout << nthElement(a, b, n) << endl; return 0; } |
Java
// Java program to find n-th number // in the sorted list of multiples // of two numbers. import java.io.*; import java.util.*; class GFG { // Return the n-th number in the sorted // list of multiples of two numbers. static int nthElement( int a, int b, int n) { ArrayList<Integer> seq = new ArrayList<Integer>(n * n + 1 ); // Generating first n multiple of a. for ( int i = 1 ; i <= n; i++) seq.add(a * i); // Sorting the sequence. Collections.sort(seq); // Generating and storing first n // multiple of b and storing if // not present in the sequence. for ( int i = 1 , k = n; i <= n && k > 0 ; i++) { // If not present in the sequence if (seq.indexOf(b * i) == - 1 ) { // Storing in the sequence. seq.add(b * i); Collections.sort(seq); k--; } } return seq.get(n - 1 ); } // Driver Code public static void main(String[] args) { int a = 3 , b = 5 , n = 5 ; System.out.println(nthElement(a, b, n)); } } // This code is contributed by mits |
Python3
# Python3 program to find n-th # number in the sorted list of # multiples of two numbers. # Return the n-th number in the # sorted list of multiples of # two numbers. def nthElement(a, b, n): seq = []; # Generating first n # multiple of a. for i in range ( 1 , n + 1 ): seq.append(a * i); # Sorting the sequence. seq.sort(); # Generating and storing first # n multiple of b and storing # if not present in the sequence. i = 1 ; k = n; while (i < = n and k > 0 ): # If not present in the sequence try : z = seq.index(b * i); except ValueError: # Storing in the sequence. seq.append(b * i); seq.sort(); k - = 1 ; i + = 1 ; return seq[n - 1 ]; # Driver Code a = 3 ; b = 5 ; n = 5 ; print (nthElement(a, b, n)); # This code is contributed by mits |
C#
// C# program to find n-th number // in the sorted list of multiples // of two numbers. using System; using System.Collections; class GFG { // Return the n-th number in the sorted // list of multiples of two numbers. static int nthElement( int a, int b, int n) { ArrayList seq = new ArrayList(); // Generating first n multiple of a. for ( int i = 1; i <= n; i++) seq.Add(a * i); // Sorting the sequence. seq.Sort(); // Generating and storing first n // multiple of b and storing if // not present in the sequence. for ( int i = 1, k = n; i <= n && k > 0; i++) { // If not present in the sequence if (!seq.Contains(b * i)) { // Storing in the sequence. seq.Add(b * i); seq.Sort(); k--; } } return ( int )seq[n - 1]; } // Driver Code static void Main() { int a = 3, b = 5, n = 5; Console.WriteLine(nthElement(a, b, n)); } } // This code is contributed by mits |
Javascript
<script> // Javascript program to find n-th number // in the sorted list of multiples // of two numbers. // Return the n-th number in the sorted // list of multiples of two numbers. function nthElement(a, b, n) { let seq = []; // Generating first n multiple of a. for (let i = 1; i <= n; i++) seq.push(a * i); // Sorting the sequence. seq.sort( function (a, b){ return a - b}); // Generating and storing first n // multiple of b and storing if // not present in the sequence. for (let i = 1, k = n; i <= n && k > 0; i++) { // If not present in the sequence if (!seq.includes(b * i)) { // Storing in the sequence. seq.push(b * i); seq.sort( function (a, b){ return a - b}); k--; } } return seq[n - 1]; } let a = 3, b = 5, n = 5; document.write(nthElement(a, b, n)); // This code is contributed by decode2207. </script> |
PHP
<?php // PHP program to find n-th number // in the sorted list of multiples // of two numbers. // Return the n-th number in the sorted // list of multiples of two numbers. function nthElement( $a , $b , $n ) { $seq = array (); // Generating first n multiple of a. for ( $i = 1; $i <= $n ; $i ++) array_push ( $seq , $a * $i ); // Sorting the sequence. sort( $seq ); // Generating and storing first // n multiple of b and storing // if not present in the sequence. for ( $i = 1, $k = $n ; $i <= $n && $k > 0; $i ++) { // If not present in the sequence if ( array_search ( $b * $i , $seq ) == 0) { // Storing in the sequence. array_push ( $seq , $b * $i ); sort( $seq ); $k --; } } return $seq [ $n - 1]; } // Driver Code $a = 3; $b = 5; $n = 5; echo nthElement( $a , $b , $n ); // This code is contributed by mits ?> |
Output:
10
Time Complexity: O(n2 log2n)
Auxiliary Space: O(n)
Method 2: (Efficient Approach)
The idea is to use the fact that common multiple of a and b are removed using LCM(a, b). Let f(a, b, x) be a function which calculates the count of number that are less than x and multiples of a and b. Now, using the inclusion-exclusion principle we can say,
f(a, b, x) : Count of number that are less than x and multiples of a and b f(a, b, x) = (x/a) + (x/b) - (x/lcm(a, b)) where (x/a) define number of multiples of a (x/b) define number of multiple of b (x/lcm(a, b)) define the number of common multiples of a and b.
Observe, a and b are constant. As x increases, f(a, b, x) will also increase. Therefore we can apply Binary Search to find the minimum value of x such that f(a, b, x) >= n. The lower bound of the function is the required answer.
The upper bound for n-th term would be min(a, b)*n. Note that we get the largest value n-th term when there are no common elements in multiples of a and b.
Below are the implementations of above approach:
C++
// C++ program to find n-th number in the // sorted list of multiples of two numbers. #include<bits/stdc++.h> using namespace std; // Return the Nth number in the sorted // list of multiples of two numbers. int nthElement( int a, int b, int n) { // Finding LCM of a and b. int lcm = (a * b)/__gcd(a,b); // Binary Search. int l = 1, r = min(a, b)*n; while (l <= r) { // Finding the middle element. int mid = (l + r)>>1; // count of number that are less than // mid and multiples of a and b int val = mid/a + mid/b - mid/lcm; if (val == n) return max((mid/a)*a, (mid/b)*b); if (val < n) l = mid + 1; else r = mid - 1; } } // Driven Program int main() { int a = 5, b = 3, n = 5; cout << nthElement(a, b, n) << endl; return 0; } |
Java
// Java program to find n-th number in the // sorted list of multiples of two numbers. import java.io.*; 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 || 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); } // Return the Nth number in the sorted // list of multiples of two numbers. static int nthElement( int a, int b, int n) { // Finding LCM of a and b. int lcm = (a * b) / __gcd(a, b); // Binary Search. int l = 1 , r = Math.min(a, b) * n; while (l <= r) { // Finding the middle element. int mid = (l + r) >> 1 ; // count of number that are less than // mid and multiples of a and b int val = mid / a + mid / b - mid / lcm; if (val == n) return Math.max((mid / a) * a, (mid / b) * b); if (val < n) l = mid + 1 ; else r = mid - 1 ; } return 0 ; } // Driver Code static public void main (String[] args) { int a = 5 , b = 3 , n = 5 ; System.out.println(nthElement(a, b, n)); } } // This code is contributed by vt_m. |
Python 3
# Python 3 program to find n-th number # in the sorted list of multiples of # two numbers. import math # Return the Nth number in the sorted # list of multiples of two numbers. def nthElement(a, b, n): # Finding LCM of a and b. lcm = (a * b) / int (math.gcd(a, b)) # Binary Search. l = 1 r = min (a, b) * n while (l < = r): # Finding the middle element. mid = (l + r) >> 1 # count of number that are less # than mid and multiples of a # and b val = ( int (mid / a) + int (mid / b) - int (mid / lcm)) if (val = = n): return int ( max ( int (mid / a) * a, int (mid / b) * b) ) if (val < n): l = mid + 1 else : r = mid - 1 # Driven Program a = 5 b = 3 n = 5 print (nthElement(a, b, n)) # This code is contributed by Smitha. |
C#
// C# program to find n-th number in the // sorted list of multiples of two numbers. 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 || 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); } // Return the Nth number in the sorted // list of multiples of two numbers. static int nthElement( int a, int b, int n) { // Finding LCM of a and b. int lcm = (a * b) / __gcd(a, b); // Binary Search. int l = 1, r = Math.Min(a, b) * n; while (l <= r) { // Finding the middle element. int mid = (l + r) >> 1; // count of number that are less than // mid and multiples of a and b int val = mid / a + mid / b - mid / lcm; if (val == n) return Math.Max((mid / a) * a, (mid / b) * b); if (val < n) l = mid + 1; else r = mid - 1; } return 0; } // Driver Code static public void Main (String []args) { int a = 5, b = 3, n = 5; Console.WriteLine(nthElement(a, b, n)); } } // This code is contributed by vt_m. |
PHP
<?php // PHP program to find n-th number // in a sorted list of multiples // of two numbers. // function to calculate gcd function gcd( $a , $b ) { return ( $a % $b ) ? gcd( $b , $a % $b ) : $b ; } // Return the Nth number in the sorted // list of multiples of two numbers. function nthElement( $a , $b , $n ) { // Finding LCM of a and b. $lcm = (int)(( $a * $b ) / gcd( $a , $b )); // Binary Search. $l = 1; $r = min( $a , $b ) * $n ; while ( $l <= $r ) { // Finding the middle element. $mid = ( $l + $r ) >> 1; // count of number that are // less than mid and multiples // of a and b $val = (int)( $mid / $a ) + (int)( $mid / $b ) - (int)( $mid / $lcm ); if ( $val == $n ) return max((int)(( $mid / $a )) * $a , (int)(( $mid / $b )) * $b ); if ( $val < $n ) $l = $mid + 1; else $r = $mid - 1; } } // Driver code $a = 5; $b = 3; $n = 5; echo nthElement( $a , $b , $n ); // This code is contributed by mits ?> |
Javascript
<script> // Javascript program to find n-th number in the // sorted list of multiples of two numbers. // Recursive function to return // gcd of a and b 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); } // Return the Nth number in the sorted // list of multiples of two numbers. function nthElement(a , b , n) { // Finding LCM of a and b. var lcm = parseInt((a * b) / __gcd(a, b)); // Binary Search. var l = 1, r = Math.min(a, b) * n; while (l <= r) { // Finding the middle element. var mid = (l + r) >> 1; // count of number that are less than // mid and multiples of a and b var val = parseInt(mid / a) + parseInt(mid / b) - parseInt(mid / lcm); if (val == n) return Math.max(parseInt(mid / a) * a, parseInt(mid / b) * b); if (val < n) l = mid + 1; else r = mid - 1; } return 0; } // Driver Code var a = 5, b = 3, n = 5; document.write(nthElement(a, b, n)); // This code contributed by shikhasingrajput </script> |
Output:
10
Time Complexity: O(log n)
Auxiliary Space: O(1)
Contact Us