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 tilesint 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 codeint 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 tilesimport 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 methodfrom 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 codeif __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> |
Output:
3
Time Complexity: O(log(min(x, y))), where x and y are two parameters of gcd.
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!