Problem Description
Given A, B and C, find Ath magical number.
Note: A number is said to be magical, if it’s divisible by B or C.
Solution
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
package com.gauk;
public class MagicNumberModded {
public static void main(String[] args) {
System.out.println(AthMagicNumber(5, 6, 3)); //10
}
//Given A, B and C, find Ath magical number.
//Note: A number is said to be magical, if it's divisible by B or C.
static long AthMagicNumber(long B, long C, long A){
//target: if we take a minimum of B and C and keep multiplying A times, we are sure that we will get at least A magical numbers. Our answer will be less than or equal to this.
//It can be lesser also, since there will be certain numbers which are multiples of the other number.
long l = 1; //We can also start with the min(B,C)
long h = Math.min(B, C) * A; //Max possible answer, since this has at least A multiples of min number.
long ans = h;
while(l<=h){
long m = (l+h)/2;
long magicalNumbersTillHere = getMagicalNumbersTillHere(B, C, A, m);
if(magicalNumbersTillHere == A){
//if number of magical numbers till mid is equal to A, then this is a potential answer.
//we should continue to check on left because the same number of magical numbers can be present on left side
ans = m;
h = m-1;
}else if(magicalNumbersTillHere < A){
//go to right
l = m+1;
}else{
//go to left
h = m-1;
}
}
return ans;
}
static long getMagicalNumbersTillHere(long B, long C, long A, long m){
long x = m/B; //number of multiples of B till m
long y = m/C; //number of multiples of C till m
long lcm = lcm(B,C); //lcm of B and C will be common till m
long z = m/lcm; //number of multiples of lcm(B,C)
long totalMagicalNumbers = x + y - z;
return totalMagicalNumbers;
}
static long lcm(long a, long b)
{
return (a / gcd(a, b)) * b;
}
static long gcd(long a, long b)
{
if (a == 0)
return b;
return gcd(b % a, a);
}
}