Facebook Pixel

Ugly Number III

Write a program to find the n-th ugly number.

Ugly numbers are positive numbers that are divisible by either a, b, or c.

Since the number can be too large, return the actual answer modulo 10^9 + 7

Example 1:

Input:n = 10, a = 2, b = 3, c = 5

Output: 14

Explanation: 2, 3, 4, 5, 6, 8, 9, 10, 12, 14 is the sequence of the first 10 ugly numbers.

Example 2:

Input:n = 2, a = 3, b = 4, c = 5

Output: 4

Explanation: 3, 4 is the sequence of the first 2 ugly numbers.

Constraints

  • 1 <= n, a, b, c <= 10^9
  • 1 <= a * b * c <= 10^18

Try it yourself

Solution

Invest in Yourself
Your new job is waiting. 83% of people that complete the program get a job offer. Unlock unlimited access to all content and features.
Go Pro