Nth Magical Number LeetCode solution in Java

1
class Solution {
2
  public int nthMagicalNumber(int n, int a, int b) {
3
    long N = (long) n;
4
    long A = (long) a;
5
    long B = (long) b;
6
    long mod = 1000000007;
7
    long min = Math.min(A, B);
8
    long low = min;
9
    long high = min * N;
10
    long ans = 0;
11
    while (low <= high) {
12
      long mid = (high - low) / 2 + low;
13
      long x = mid / A + mid / B - mid / lcm(A, B);
14
      if (x >= N) {
15
        ans = mid;
16
        high = mid - 1;
17
      } else if (x < N) {
18
        low = mid + 1;
19
      } else {
20
        high = mid - 1;
21
      }
22
    }
23

24
    ans = ans % mod;
25
    return (int) ans;
26
  }
27

28
  long lcm(long a, long b) {
29
    long tmpA = a;
30
    long tmpB = b;
31
    while (a > 0) {
32
      long temp = a;
33
      a = b % a;
34
      b = temp;
35
    }
36

37
    return tmpA * tmpB / b;
38
  }
39
}