1
// This is a typical Binary Search Problem Here I did Binary Search and
2
// Optimized my lcm function a lot. Here Number of Ugly numbers for any number
3
// is that number/a + that number/b + that number/c + that number/lcm(a,b,c) -
4
// that number/lcm(a,b) - that number/lcm(b,c) - that number/(a,c) and howzz
5
// that?? See Lets suppose that number is 17 for which you are checking values
6
// and a = 2 , b=3 and c= 4 now figure out all the possible values for a =
7
// 2,4,6,8,10,12,14,16 b = 3,6,9,12,15 c = 4,8,12,16 Now if we add them all we
8
// can see 4,6,8,16 are coming twice and 12 is coming thrice so we do lcm(2,3) =
9
// 6 then we are basically multiple occurance of numbers divisible by 6 simlarly
10
// for lcm(2,4) & lcm(3,4) but any number which is divisble by all three of them
11
// we have deleted it 3 times we need at least so we are adding numbers which
12
// are divisble by lcm(2,3,4) which is 12 here So if suppose we are countering
13
// more numbers than n then h = mid-1 we need to move backward else we need to
14
// forward.
15
class Solution {
16
 public:
17
#define ll long long
18
  ll gcd(ll a, ll b) {
19
    if (b == 0) return a;
20
    return gcd(b, a % b);
21
  }
22
  ll lcm(ll a, ll b) {
23
    return (a / gcd(a, b)) * b;
24
  }
25
  bool check(ll mid, int a, int b, int c, int n) {
26
    ll j1 = lcm(a, b);
27
    ll j2 = lcm(a, c);
28
    ll j3 = lcm(b, c);
29
    ll j4 = lcm(j1, c);
30
    ll k = mid / a + mid / b + mid / c + mid / j4 - (mid / j1 + mid / j2 + mid / j3);
31
    return k == n;
32
  }
33
  bool check1(ll mid, int a, int b, int c, int n) {
34
    ll j1 = lcm(a, b);
35
    ll j2 = lcm(a, c);
36
    ll j3 = lcm(b, c);
37
    ll j4 = lcm(j1, c);
38
    ll k = mid / a + mid / b + mid / c + mid / j4 - (mid / j1 + mid / j2 + mid / j3);
39
    return k >= n;
40
  }
41
  int nthUglyNumber(int n, int a, int b, int c) {
42
    ll l = min(a, min(b, c));
43
    ll h = INT_MAX;
44
    while (l <= h) {
45
      ll mid = l + (h - l) / 2;
46
      if (check(mid, a, b, c, n) && (mid % a == 0 || mid % b == 0 || mid % c == 0)) {
47
        return mid;
48
      } else {
49
        if (check1(mid, a, b, c, n)) {
50
          h = mid - 1;
51
        } else {
52
          l = mid + 1;
53
        }
54
      }
55
    }
56
    return 1;
57
  }
58
};