Write a program to find the n-th ugly number.
Ugly numbers are positive integers which are divisible by a or b or c.
 
Example 1:
Input: n = 3, a = 2, b = 3, c = 5
Output: 4
Explanation: The ugly numbers are 2, 3, 4, 5, 6, 8, 9, 10... The 3rd is 4.
Example 2:
Input: n = 4, a = 2, b = 3, c = 4
Output: 6
Explanation: The ugly numbers are 2, 3, 4, 6, 8, 9, 10, 12... The 4th is 6.

Example 3:
Input: n = 5, a = 2, b = 11, c = 13
Output: 10
Explanation: The ugly numbers are 2, 4, 6, 8, 10, 11, 12, 13... The 5th is 10.

Example 4:
Input: n = 1000000000, a = 2, b = 217983653, c = 336916467
Output: 1999999984

 
Constraints:

1 <= n, a, b, c <= 10^9
1 <= a * b * c <= 10^18
It's guaranteed that the result will be in range [1, 2 * 10^9]

Source: leetcode | Difficulty: MEDIUM_HARD
Tags: Number theory

Sorting

Mathematics

Starter code: class Solution:
    def nthUglyNumber(self, n: int, a: int, b: int, c: int) -> int:
        

Solutions:
class Solution:

	def nthUglyNumber(self, n: int, a: int, b: int, c: int) -> int:

		def enough(num):
			total = num // a + num // b + num // c - num // ab - num // bc - num // ac + num // abc
			return total >= n
		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)
		(left, right) = (1, min(a, b, c) * n)
		while left < right:
			mid = left + (right - left) // 2
			if enough(mid):
				right = mid
			else:
				left = mid + 1
		return left


class Solution:

	def nthUglyNumber(self, n: int, a: int, b: int, c: int) -> int:
		ab = a * b // math.gcd(a, b)
		bc = b * c // math.gcd(b, c)
		ca = a * c // math.gcd(c, a)
		abc = ab * c // math.gcd(ab, c)
		lo = 1
		hi = 2 * 10 ** 9
		while lo < hi:
			m = (lo + hi) // 2
			cnt = m // a + m // b + m // c - m // ab - m // bc - m // ca + m // abc
			if cnt < n:
				lo = m + 1
			else:
				hi = m
		return lo


class Solution:

	def nthUglyNumber(self, n: int, a: int, b: int, c: int) -> int:

		def lcm(a, b):
			return a * b // math.gcd(a, b)
		nums = sorted([a, b, c])
		nums2 = [lcm(a, b), lcm(b, c), lcm(a, c)]
		nums3 = lcm(nums2[0], c)
		(lo, hi) = (n, nums[-1] * n)
		while lo < hi:
			mid = (lo + hi) // 2
			rank = sum((mid // n for n in nums)) - sum((mid // n for n in nums2)) + mid // nums3
			if rank < n:
				lo = mid + 1
			else:
				hi = mid
		return lo


class Solution:

	def nthUglyNumber(self, n: int, a: int, b: int, c: int) -> int:
		ab = a * b // math.gcd(a, b)
		bc = b * c // math.gcd(c, b)
		ac = a * c // math.gcd(a, c)
		abc = ab * c // math.gcd(ab, c)

		def nthUgly(k: int) -> bool:
			h = k // a + k // b + k // c - k // ab - k // ac - k // bc + k // abc
			if h >= n:
				return True
			return False
		(left, right) = (1, 10 ** 10)
		while left < right:
			mid = (right + left) // 2
			if nthUgly(mid):
				right = mid
			else:
				left = mid + 1
		return left


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 = ab * c // math.gcd(ab, c)

		def has_nsmaller(num):
			k = num // a + num // b + num // c - num // ac - num // ab - num // bc + num // abc
			return k >= n
		(low, high) = (0, 2 * 10 ** 9)
		while low < high:
			mid = (low + high) // 2
			if has_nsmaller(mid):
				high = mid
			else:
				low = mid + 1
		return low


class Solution:

	def nthUglyNumber(self, n: int, a: int, b: int, c: int) -> int:

		def gcd(a, b):
			while b:
				(a, b) = (b, a % b)
			return a

		def lcm(a, b):
			return a * b // gcd(a, b)

		def count_ugly(N, a, b, c):
			(ab, ac, bc) = (lcm(a, b), lcm(a, c), lcm(b, c))
			abc = lcm(ab, c)
			return N // a + N // b + N // c - N // ab - N // ac - N // bc + N // abc
		(s, e) = (1, 2 * 10 ** 9)
		while s <= e:
			m = s + (e - s) // 2
			cnt = count_ugly(m, a, b, c)
			if cnt >= n:
				e = m - 1
			else:
				s = m + 1
		return s


class Solution:

	def nthUglyNumber(self, n: int, a: int, b: int, c: int) -> int:
		ab = a * b // gcd(a, b)
		bc = b * c // gcd(b, c)
		ca = c * a // gcd(c, a)
		abc = ab * c // gcd(ab, c)

		def fn(k):
			return k // a + k // b + k // c - k // ab - k // bc - k // ca + k // abc
		(lo, hi) = (0, 2000000000)
		while lo < hi:
			mid = (lo + hi) // 2
			if fn(mid) >= n:
				hi = mid
			else:
				lo = mid + 1
		return lo