Count of common multiples of two numbers in a range
Given a range from L to R and every Xth tile is painted black and every Yth tile is painted white in that range from L to R. If a tile is painted both white and black, then it is considered to be painted grey. The task is to find the number of tiles that are colored grey in range L to R (both inclusive).
Examples:
Input: X = 2, Y = 3, L = 6, R = 18 Output: 3 The grey coloured tiles are numbered 6, 12, 18 Input: X = 1, Y = 4, L = 5, R = 10 Output: 1 The only grey coloured tile is 8.
Approach: Since every multiple of X is black and every multiple of Y is white. Any tile which is a multiple of both X and Y would be grey. The terms that are divisible by both X and Y are the terms that are divisible by the lcm of X and Y.
Lcm can be found out using the following formula:
lcm = (x*y) / gcd(x, y)
GCD can be computed in logn time using Euclid’s algorithm. The number of multiples of lcm in range L to R can be found by using a common trick of:
count(L, R) = count(R) - count(L-1)
Number of terms divisible by K less than N is:
floor(N/K)
Below is the implementation to find the number of grey tiles:
C++
// C++ implementation to find the number of // grey tiles #include <bits/stdc++.h> using namespace std; // Function to count the number of grey tiles int findTileCount( int x, int y, int l, int r) { int lcm = (x * y) / __gcd(x, y); // Number multiple of lcm less than L int countl = (l - 1) / lcm; // Number of multiples of lcm less than R+1 int countr = r / lcm; return countr - countl; } // Driver code int main() { int x = 2, y = 3, l = 6, r = 18; cout << findTileCount(x, y, l, r); return 0; } |
Java
// Java implementation to find the // number of grey tiles import java.io.*; class GFG { // Function to count the number // of grey tiles static int findTileCount( int x, int y, int l, int r) { int lcm = (x * y) / __gcd(x, y); // Number multiple of lcm less than L int countl = (l - 1 ) / lcm; // Number of multiples of // lcm less than R+1 int countr = r / lcm; return countr - countl; } 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); } // Driver code public static void main (String[] args) { int x = 2 , y = 3 , l = 6 , r = 18 ; System.out.println(findTileCount(x, y, l, r)); } } // This code is contributed ajit |
Python3
# Python3 implementation to find the number of # grey tiles # from math lib import gcd method from math import gcd # Function to count the number of grey tiles def findTileCount(x, y, l, r) : lcm = (x * y) / / gcd(x, y) # Number multiple of lcm less than L count1 = (l - 1 ) / / lcm # Number of multiples of lcm less than R+1 countr = r / / lcm return countr - count1 # Driver code if __name__ = = "__main__" : x, y, l, r = 2 , 3 , 6 , 18 print (findTileCount(x, y, l, r)) # This code is contributed by # ANKITRAI1 |
C#
// C# implementation to find the // number of grey tiles using System; class GFG { // Function to count the number // of grey tiles static int findTileCount( int x, int y, int l, int r) { int lcm = (x * y) / __gcd(x, y); // Number multiple of lcm less than L int countl = (l - 1) / lcm; // Number of multiples of // lcm less than R+1 int countr = r / lcm; return countr - countl; } 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); } // Driver code public static void Main() { int x = 2, y = 3, l = 6, r = 18; Console.Write(findTileCount(x, y, l, r)); } } // This code is contributed // by Kirti_Mangal |
PHP
<?php // PHP implementation to find the // number of grey tiles // Function to count the number // of grey tiles function findTileCount( $x , $y , $l , $r ) { $lcm = (int)(( $x * $y ) / __gcd( $x , $y )); // Number multiple of lcm less than L $countl = (int)(( $l - 1) / $lcm ); // Number of multiples of // lcm less than R+1 $countr = (int)( $r / $lcm ); return $countr - $countl ; } function __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 ); } // Driver code $x = 2; $y = 3; $l = 6; $r = 18; echo findTileCount( $x , $y , $l , $r ); // This code is contributed // by Akanksha Rai(Abby_akku) ?> |
Javascript
<script> // JavaScript implementation to find the // number of grey tiles // Function to count the number // of grey tiles function findTileCount(x,y,l,r) { lcm = parseInt((x * y) / __gcd(x, y)); // Number multiple of lcm less than L countl = parseInt((l - 1) / lcm); // Number of multiples of // lcm less than R+1 countr = parseInt(r / lcm); return countr - countl; } function __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); } // Driver code let x = 2; let y = 3; let l = 6; let r = 18; document.write(findTileCount(x, y, l, r)); // This code is contributed by bobby </script> |
3
Time Complexity: O(log(min(x, y))), where x and y are two parameters of gcd.
Contact Us