Count N digit numbers divisible by both given numbers X and Y
Given X, Y, and N. Find the number of N digit integers divisible by both X and Y.
Examples:
Input: N = 2, X = 5, Y = 7
Output: 2
Explanation: There are only 2 two-digit numbers divisible by both 5 and 7. They are 35 and 70.Input: N = 1, X = 2, Y = 3
Output: 1
Explanation: 6 is the only 1-digit number divisible by both 2 and 3.
Approach: This can be solved with the following idea:
LCM of two numbers denotes the lowest number that is divisible by both numbers.
Below are the steps involved:
- Find the LCM of X and Y.
- Initialize a variable ans.
- Divide 10^N by LCM and store it in ans which denotes total numbers divisible by LCM up to 10^N.
- subtract 10^(N-1) / LCM from ans.
- Output ans.
Below is the implementation of the above approach:
C++
// C++ Implementation #include <bits/stdc++.h> #include <iostream> using namespace std; // Function to calculate GCD of two numbers int gcd( int x, int y) { while (y) { int temp = x % y; x = y; y = temp; } return x; } // Function to calculate LCM of two numbers int lcm( int x, int y) { return (x * y) / gcd(x, y); } // Function to calculate x^y modulo p long long power( long long x, int y) { long long res = 1; // Initialize result if (x == 0) return 0; // In case x is divisible by p; while (y > 0) { // If y is odd, multiply x with result if (y & 1) res = (res * x); // y must be even now y = y >> 1; // y = y/2 x = (x * x); } return res; } // Function to count number of N digits long long divCount( int N, int X, int Y) { // Finding the number of digits divisible by 10 ^ N long long ans = (power(10ll, N) - 1) / (lcm(X, Y)); // Find the floor ans -= (power(10ll, N - 1) - 1) / (lcm(X, Y)); return ans; } // Driver code int main() { int N = 5; int X = 2; int Y = 4; // Function call cout << divCount(N, X, Y); return 0; } |
Java
import java.util.*; class GFG { // Function to calculate GCD of two numbers static int gcd( int x, int y) { while (y != 0 ) { int temp = x % y; x = y; y = temp; } return x; } // Function to calculate LCM of two numbers static int lcm( int x, int y) { return (x * y) / gcd(x, y); } // Function to calculate x^y modulo p static long power( long x, int y) { long res = 1 ; // Initialize result if (x == 0 ) return 0 ; // In case x is divisible by p; while (y > 0 ) { // If y is odd, multiply x with result if ((y & 1 ) == 1 ) res = (res * x); // y must be even now y = y >> 1 ; // y = y/2 x = (x * x); } return res; } // Function to count number of N digits static long divCount( int N, int X, int Y) { // Finding the number of digits divisible by 10 ^ N long ans = (power( 10 , N) - 1 ) / (lcm(X, Y)); // Find the floor ans -= (power( 10 , N - 1 ) - 1 ) / (lcm(X, Y)); return ans; } // Driver code public static void main(String[] args) { Scanner sc = new Scanner(System.in); int N = 5 ; int X = 2 ; int Y = 4 ; // Function call System.out.println(divCount(N, X, Y)); sc.close(); } } |
Python3
# Function to calculate GCD of two numbers def gcd(x, y): while y: temp = x % y x = y y = temp return x # Function to calculate LCM of two numbers def lcm(x, y): return (x * y) / / gcd(x, y) # Function to calculate x^y modulo p def power(x, y): res = 1 # Initialize result if x = = 0 : return 0 # In case x is divisible by p; while y > 0 : # If y is odd, multiply x with result if y & 1 : res = (res * x) # y must be even now y = y >> 1 # y = y/2 x = (x * x) return res # Function to count number of N digits def div_count(N, X, Y): # Finding the number of digits divisible by 10 ^ N ans = (power( 10 , N) - 1 ) / / (lcm(X, Y)) # Find the floor ans - = (power( 10 , N - 1 ) - 1 ) / / (lcm(X, Y)) return ans # Driver code if __name__ = = "__main__" : N = 5 X = 2 Y = 4 # Function call print (div_count(N, X, Y)) |
C#
// C# program for the above approach using System; public class GFG { // Function to calculate GCD of two numbers static int GCD( int x, int y) { while (y != 0) { int temp = x % y; x = y; y = temp; } return x; } // Function to calculate LCM of two numbers static int LCM( int x, int y) => (x * y) / GCD(x, y); // Function to calculate x^y modulo p static long Power( long x, int y) { long res = 1; if (x == 0) return 0; // In case x is divisible by p; while (y > 0) { if ((y & 1) == 1) res = (res * x); y = y >> 1; // y = y/2 x = (x * x); } return res; } // Function to count the number of N digits static long DivCount( int N, int X, int Y) { // Finding the number of digits divisible by 10 ^ N long ans = (Power(10, N) - 1) / (LCM(X, Y)); // Find the floor ans -= (Power(10, N - 1) - 1) / (LCM(X, Y)); return ans; } // Driver code static void Main() { int N = 5; int X = 2; int Y = 4; // Function call Console.WriteLine(DivCount(N, X, Y)); } } // This code is contributed by Susobhan Akhuli |
Javascript
// javaScript code for the above approach // Function to calculate GCD of two numbers function gcd(x, y) { while (y) { const temp = x % y; x = y; y = temp; } return x; } // Function to calculate LCM of two numbers function lcm(x, y) { return (x * y) / gcd(x, y); } // Function to calculate x^y modulo p function power(x, y) { // Initialize result let res = 1; if (x === 0) { // In case x is divisible by p return 0; } while (y > 0) { // If y is odd, multiply x with result if (y % 2 == 1) { res = (res * x); } // y must be even now // y = y/2 y = y >> 1; x = (x * x); } return res; } // Function to count number of N digits function divCount(N, X, Y) { // Finding the number of digits // divisible by 10 ^ N let ans = (power(10, N) - 1) / (lcm(X, Y)); // Find the floor ans -= (power(10, N - 1) - 1) / (lcm(X, Y)); return ans; } // Driver code const N = 5; const X = 2; const Y = 4; // Function call and display result console.log(divCount(N, X, Y)); |
Output
22500
Complexity Analysis:
Time Complexity: O(log N)
Auxiliary Space: O(1)
Contact Us