|
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++
#include <bits/stdc++.h>
#include <iostream>
using namespace std;
int gcd(int x, int y)
{
while (y) {
int temp = x % y;
x = y;
y = temp;
}
return x;
}
int lcm(int x, int y) { return (x * y) / gcd(x, y); }
long long power(long long x, int y)
{
long long res = 1;
if (x == 0)
return 0;
while (y > 0) {
if (y & 1)
res = (res * x);
y = y >> 1;
x = (x * x);
}
return res;
}
long long divCount(int N, int X, int Y)
{
long long ans = (power(10ll, N) - 1) / (lcm(X, Y));
ans -= (power(10ll, N - 1) - 1) / (lcm(X, Y));
return ans;
}
int main()
{
int N = 5;
int X = 2;
int Y = 4;
cout << divCount(N, X, Y);
return 0;
}
|
Java
import java.util.*;
class GFG {
static int gcd(int x, int y) {
while (y != 0) {
int temp = x % y;
x = y;
y = temp;
}
return x;
}
static int lcm(int x, int y) {
return (x * y) / gcd(x, y);
}
static long power(long x, int y) {
long res = 1;
if (x == 0)
return 0;
while (y > 0) {
if ((y & 1) == 1)
res = (res * x);
y = y >> 1;
x = (x * x);
}
return res;
}
static long divCount(int N, int X, int Y) {
long ans = (power(10, N) - 1) / (lcm(X, Y));
ans -= (power(10, N - 1) - 1) / (lcm(X, Y));
return ans;
}
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int N = 5;
int X = 2;
int Y = 4;
System.out.println(divCount(N, X, Y));
sc.close();
}
}
|
Python3
def gcd(x, y):
while y:
temp = x % y
x = y
y = temp
return x
def lcm(x, y):
return (x * y) // gcd(x, y)
def power(x, y):
res = 1
if x == 0:
return 0
while y > 0:
if y & 1:
res = (res * x)
y = y >> 1
x = (x * x)
return res
def div_count(N, X, Y):
ans = (power(10, N) - 1) // (lcm(X, Y))
ans -= (power(10, N - 1) - 1) // (lcm(X, Y))
return ans
if __name__ == "__main__":
N = 5
X = 2
Y = 4
print(div_count(N, X, Y))
|
C#
using System;
public class GFG {
static int GCD(int x, int y)
{
while (y != 0) {
int temp = x % y;
x = y;
y = temp;
}
return x;
}
static int LCM(int x, int y) => (x * y) / GCD(x, y);
static long Power(long x, int y)
{
long res = 1;
if (x == 0)
return 0;
while (y > 0) {
if ((y & 1) == 1)
res = (res * x);
y = y >> 1;
x = (x * x);
}
return res;
}
static long DivCount(int N, int X, int Y)
{
long ans = (Power(10, N) - 1) / (LCM(X, Y));
ans -= (Power(10, N - 1) - 1) / (LCM(X, Y));
return ans;
}
static void Main()
{
int N = 5;
int X = 2;
int Y = 4;
Console.WriteLine(DivCount(N, X, Y));
}
}
|
Javascript
function gcd(x, y) {
while (y) {
const temp = x % y;
x = y;
y = temp;
}
return x;
}
function lcm(x, y) {
return (x * y) / gcd(x, y);
}
function power(x, y) {
let res = 1;
if (x === 0) {
return 0;
}
while (y > 0) {
if (y % 2 == 1) {
res = (res * x);
}
y = y >> 1;
x = (x * x);
}
return res;
}
function divCount(N, X, Y) {
let ans = (power(10, N) - 1) / (lcm(X, Y));
ans -= (power(10, N - 1) - 1) / (lcm(X, Y));
return ans;
}
const N = 5;
const X = 2;
const Y = 4;
console.log(divCount(N, X, Y));
|
Complexity Analysis:
Time Complexity: O(log N)
Auxiliary Space: O(1)
|
