# 1201. Ugly Number III

• Time:
• Space:
  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 class Solution { public: int nthUglyNumber(int n, long a, long b, long c) { const long ab = a * b / __gcd(a, b); const long ac = a * c / __gcd(a, c); const long bc = b * c / __gcd(b, c); const long abc = a * bc / __gcd(a, bc); int l = 1; int r = 2'000'000'000; while (l < r) { const int m = l + (r - l) / 2; if (m / a + m / b + m / c - m / ab - m / ac - m / bc + m / abc >= n) r = m; else l = m + 1; } return l; } }; 
  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 class Solution { public int nthUglyNumber(int n, long a, long b, long c) { final long ab = a * b / gcd(a, b); final long ac = a * c / gcd(a, c); final long bc = b * c / gcd(b, c); final long abc = a * bc / gcd(a, bc); int l = 1; int r = 2_000_000_000; while (l < r) { final int m = (l + r) / 2; if (m / a + m / b + m / c - m / ab - m / ac - m / bc + m / abc >= n) r = m; else l = m + 1; } return l; } private long gcd(long a, long b) { return b == 0 ? a : gcd(b, a % b); } } 
 1 2 3 4 5 6 7 8 9 class Solution: def nthUglyNumber(self, n: int, a: int, b: int, c: int) -> int: ab = a * b // math.gcd(a, b) ac = a * c // math.gcd(a, c) bc = b * c // math.gcd(b, c) abc = a * bc // math.gcd(a, bc) return bisect.bisect_left( range(2 * 10**9), n, key=lambda m: m // a + m // b + m // c - m // ab - m // ac - m // bc + m // abc)