text: ##### Welcome to Subscribe On Youtube
  
  Formatted question description: https://leetcode.ca/all/1201.html
  
  # 1201. Ugly Number III
  
  Medium
  
  ## Description
  
  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]
  
  ## Solution
  
  Use binary search. Initially set low to be 1 and high to be 2 * 10^9. The condition of binary search is low < high. Each time set mid to be the average of low and high, and calculate the number of ugly numbers that are less than or equal to mid, which can be calculated using inclusion-exclusion principle. If the number of ugly numbers is less than n, then obviously the n-th ugly number is greater than mid, so set low = mid + 1. Otherwise, the n-th ugly number may be mid or less than mid, so set high = mid. After the search ends, return low.
  
  • class Solution {
  public int nthUglyNumber(int n, int a, int b, int c) {
  long lcmAB = a / gcd(a, b) * b;
  long lcmBC = b / gcd(b, c) * c;
  long lcmAC = a / gcd(a, c) * c;
  long lcmABC = lcmAB / gcd(lcmAB, c) * c;
  long low = 1, high = 2000000000;
  while (low < high) {
  long mid = (high - low) / 2 + low;
  long count = mid / a + mid / b + mid / c - mid / lcmAB - mid / lcmBC - mid / lcmAC + mid / lcmABC;
  if (count < n)
  low = mid + 1;
  else
  high = mid;
  }
  return (int) low;
  }
  
  public long gcd(long a, long b) {
  if (a == 0 && b == 0)
  return 1;
  while (a != 0 && b != 0) {
  if (a > b) {
  long temp = a;
  a = b;
  b = temp;
  }
  b %= a;
  }
  return a == 0 ? b : a;
  }
  }
  
  • // OJ: https://leetcode.com/problems/ugly-number-iii/
  // Time: O(logN)
  // Space: O(1)
  class Solution {
  long lcm(long a, long b) { // least common multiple
  return a * b / gcd(a, b);
  }
  public:
  int nthUglyNumber(int n, int a, int b, int c) {
  long L = 1, R = 2e9;
  auto le = [&](long M) {
  return M / a + M / b + M / c - M / lcm(a, b) - M / lcm(b, c) - M / lcm(a, c) + M / lcm(lcm(a, b), c);
  };
  while (L <= R) {
  long M = (L + R) / 2, cnt = le(M);
  if (cnt < n) L = M + 1;
  else R = M - 1;
  }
  return L;
  }
  };
  
  • class Solution:
  def f(self, num: int, a: int, b: int, c: int) -> int:
  return (
  num // a
  + num // b
  + num // c
  - num // math.lcm(a, b)
  - num // math.lcm(a, c)
  - num // math.lcm(b, c)
  + num // math.lcm(a, b, c)
  )
  
  def nthUglyNumber(self, n: int, a: int, b: int, c: int) -> int:
  left, right = 1, int(2e9)
  while left <= right:
  mid = left + (right - left) // 2
  if self.f(mid, a, b, c) < n:
  left = mid + 1
  else:
  right = mid - 1
  return left
  
  ############
  
  # 1201. Ugly Number III
  # https://leetcode.com/problems/ugly-number-iii
  
  class Solution:
  def nthUglyNumber(self, n: int, a: int, b: int, c: int) -> int:
  
  def enough(x):
  total = (x // a) + (x // b) + (x // c) - (x // ab) - (x // bc) - (x // ac) + (x // abc)
  
  ab = a*b // math.gcd(a,b)
  bc = b*c // math.gcd(b,c)
  ac = a*c // math.gcd(a,c)
  abc = a*bc // math.gcd(a,bc)
  
  left, right = 1, 10 ** 10
  while left < right:
  mid = left + (right-left) // 2
  
  if enough(mid):
  right = mid
  else:
  left = mid + 1
  
  return left
  
  
  • func nthUglyNumber(n int, a int, b int, c int) int {
  left, right := 1, int(2e9)
  for left <= right {
  mid := left + (right-left)/2
  if f(mid, a, b, c) < n {
  left = mid + 1
  } else {
  right = mid - 1
  }
  }
  return left
  }
  
  func f(num int, a int, b int, c int) int {
  return num/a + num/b + num/c - num/lcm(a, b) - num/lcm(a, c) - num/lcm(b, c) + num/lcm(lcm(a, b), c)
  }
  
  // Least common multiple
  func lcm(a, b int) int {
  // Greatest common divisor
  gcd := func(x, y int) int {
  for y != 0 {
  if x < y {
  x, y = y, x
  }
  x, y = y, x%y
  }
  return x
  }
  return a * b / gcd(a, b)
  }
  
  • function nthUglyNumber(n: number, a: number, b: number, c: number): number {
  const ab = lcm(BigInt(a), BigInt(b));
  const bc = lcm(BigInt(b), BigInt(c));
  const ac = lcm(BigInt(a), BigInt(c));
  const abc = lcm(BigInt(a), bc);
  let l = 1n;
  let r = BigInt(2e9);
  while (l < r) {
  const mid = (l + r) >> 1n;
  const count =
  mid / BigInt(a) +
  mid / BigInt(b) +
  mid / BigInt(c) -
  mid / ab -
  mid / bc -
  mid / ac +
  mid / abc;
  if (count >= BigInt(n)) {
  r = mid;
  } else {
  l = mid + 1n;
  }
  }
  return Number(l);
  }
  
  function gcd(a: bigint, b: bigint): bigint {
  return b === 0n ? a : gcd(b, a % b);
  }
  
  function lcm(a: bigint, b: bigint): bigint {
  return (a * b) / gcd(a, b);
  }
explanation: The provided text is a detailed description of a programming problem from LeetCode, specifically problem 1201, "Ugly Number III." The document includes the problem statement, examples, constraints, and multiple solutions in different programming languages (Java, C++, Python, Go, and TypeScript). The problem involves finding the n-th ugly number, which is defined as a positive integer divisible by a, b, or c.
  
  The document contains multiple questions in the form of examples, each with an input and an expected output. These examples serve as test cases for the problem.
distilabel_metadata.content: Evaluate the user given text extract and determine if it contains a math question and optionally and answer to this question.
  
  Output rules:
  
  1. Briefly describe the document and mention if it contains a question or a question and answer.
  2. Finalize the output with: Label: no-question,question,question-and-answer,multiple-question,multiple-question-and-answer
distilabel_metadata.role: system
distilabel_metadata.content: ##### Welcome to Subscribe On Youtube
  
  Formatted question description: https://leetcode.ca/all/1201.html
  
  # 1201. Ugly Number III
  
  Medium
  
  ## Description
  
  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]
  
  ## Solution
  
  Use binary search. Initially set low to be 1 and high to be 2 * 10^9. The condition of binary search is low < high. Each time set mid to be the average of low and high, and calculate the number of ugly numbers that are less than or equal to mid, which can be calculated using inclusion-exclusion principle. If the number of ugly numbers is less than n, then obviously the n-th ugly number is greater than mid, so set low = mid + 1. Otherwise, the n-th ugly number may be mid or less than mid, so set high = mid. After the search ends, return low.
  
  • class Solution {
  public int nthUglyNumber(int n, int a, int b, int c) {
  long lcmAB = a / gcd(a, b) * b;
  long lcmBC = b / gcd(b, c) * c;
  long lcmAC = a / gcd(a, c) * c;
  long lcmABC = lcmAB / gcd(lcmAB, c) * c;
  long low = 1, high = 2000000000;
  while (low < high) {
  long mid = (high - low) / 2 + low;
  long count = mid / a + mid / b + mid / c - mid / lcmAB - mid / lcmBC - mid / lcmAC + mid / lcmABC;
  if (count < n)
  low = mid + 1;
  else
  high = mid;
  }
  return (int) low;
  }
  
  public long gcd(long a, long b) {
  if (a == 0 && b == 0)
  return 1;
  while (a != 0 && b != 0) {
  if (a > b) {
  long temp = a;
  a = b;
  b = temp;
  }
  b %= a;
  }
  return a == 0 ? b : a;
  }
  }
  
  • // OJ: https://leetcode.com/problems/ugly-number-iii/
  // Time: O(logN)
  // Space: O(1)
  class Solution {
  long lcm(long a, long b) { // least common multiple
  return a * b / gcd(a, b);
  }
  public:
  int nthUglyNumber(int n, int a, int b, int c) {
  long L = 1, R = 2e9;
  auto le = [&](long M) {
  return M / a + M / b + M / c - M / lcm(a, b) - M / lcm(b, c) - M / lcm(a, c) + M / lcm(lcm(a, b), c);
  };
  while (L <= R) {
  long M = (L + R) / 2, cnt = le(M);
  if (cnt < n) L = M + 1;
  else R = M - 1;
  }
  return L;
  }
  };
  
  • class Solution:
  def f(self, num: int, a: int, b: int, c: int) -> int:
  return (
  num // a
  + num // b
  + num // c
  - num // math.lcm(a, b)
  - num // math.lcm(a, c)
  - num // math.lcm(b, c)
  + num // math.lcm(a, b, c)
  )
  
  def nthUglyNumber(self, n: int, a: int, b: int, c: int) -> int:
  left, right = 1, int(2e9)
  while left <= right:
  mid = left + (right - left) // 2
  if self.f(mid, a, b, c) < n:
  left = mid + 1
  else:
  right = mid - 1
  return left
  
  ############
  
  # 1201. Ugly Number III
  # https://leetcode.com/problems/ugly-number-iii
  
  class Solution:
  def nthUglyNumber(self, n: int, a: int, b: int, c: int) -> int:
  
  def enough(x):
  total = (x // a) + (x // b) + (x // c) - (x // ab) - (x // bc) - (x // ac) + (x // abc)
  
  ab = a*b // math.gcd(a,b)
  bc = b*c // math.gcd(b,c)
  ac = a*c // math.gcd(a,c)
  abc = a*bc // math.gcd(a,bc)
  
  left, right = 1, 10 ** 10
  while left < right:
  mid = left + (right-left) // 2
  
  if enough(mid):
  right = mid
  else:
  left = mid + 1
  
  return left
  
  
  • func nthUglyNumber(n int, a int, b int, c int) int {
  left, right := 1, int(2e9)
  for left <= right {
  mid := left + (right-left)/2
  if f(mid, a, b, c) < n {
  left = mid + 1
  } else {
  right = mid - 1
  }
  }
  return left
  }
  
  func f(num int, a int, b int, c int) int {
  return num/a + num/b + num/c - num/lcm(a, b) - num/lcm(a, c) - num/lcm(b, c) + num/lcm(lcm(a, b), c)
  }
  
  // Least common multiple
  func lcm(a, b int) int {
  // Greatest common divisor
  gcd := func(x, y int) int {
  for y != 0 {
  if x < y {
  x, y = y, x
  }
  x, y = y, x%y
  }
  return x
  }
  return a * b / gcd(a, b)
  }
  
  • function nthUglyNumber(n: number, a: number, b: number, c: number): number {
  const ab = lcm(BigInt(a), BigInt(b));
  const bc = lcm(BigInt(b), BigInt(c));
  const ac = lcm(BigInt(a), BigInt(c));
  const abc = lcm(BigInt(a), bc);
  let l = 1n;
  let r = BigInt(2e9);
  while (l < r) {
  const mid = (l + r) >> 1n;
  const count =
  mid / BigInt(a) +
  mid / BigInt(b) +
  mid / BigInt(c) -
  mid / ab -
  mid / bc -
  mid / ac +
  mid / abc;
  if (count >= BigInt(n)) {
  r = mid;
  } else {
  l = mid + 1n;
  }
  }
  return Number(l);
  }
  
  function gcd(a: bigint, b: bigint): bigint {
  return b === 0n ? a : gcd(b, a % b);
  }
  
  function lcm(a: bigint, b: bigint): bigint {
  return (a * b) / gcd(a, b);
  }
distilabel_metadata.role: user
distilabel_metadata.raw_output_q_a_detector_0: The provided text is a detailed description of a programming problem from LeetCode, specifically problem 1201, "Ugly Number III." The document includes the problem statement, examples, constraints, and multiple solutions in different programming languages (Java, C++, Python, Go, and TypeScript). The problem involves finding the n-th ugly number, which is defined as a positive integer divisible by a, b, or c.
  
  The document contains multiple questions in the form of examples, each with an input and an expected output. These examples serve as test cases for the problem.
  
  Label: multiple-question-and-answer