Welcome to Subscribe On Youtube

Formatted question description: https://leetcode.ca/all/1201.html

1201. Ugly Number III

Level

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)
            return total >= n
            
        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);
}

All Problems

All Solutions