##### 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);
}
The text passage contains a problem statement for a programming challenge, specifically to find the n-th ugly number that is divisible by a, b, or c. It includes multiple examples with inputs and corresponding outputs, and a solution using binary search and the inclusion-exclusion principle.
multiple_questions_with_answers
Given a text passage, determine:
    1. If it contains a mathematical question (including word problems or calculations)
    2. If an answer to that mathematical question is provided in the text

First, describe the content structure you found in 1-2 sentences.

Then provide your analysis in the following format:
TYPE: <one of the following values>
- NO_QUESTION
- SINGLE_QUESTION
- SINGLE_QUESTION_WITH_ANSWER
- MULTIPLE_QUESTIONS
- MULTIPLE_QUESTIONS_WITH_ANSWERS
system
##### 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);
}
user
The text passage contains a problem statement for a programming challenge, specifically to find the n-th ugly number that is divisible by a, b, or c. It includes multiple examples with inputs and corresponding outputs, and a solution using binary search and the inclusion-exclusion principle.

TYPE: MULTIPLE_QUESTIONS_WITH_ANSWERS