Write a program to find the n -th ugly number.
Ugly numbers are positive numbers whose prime factors only include 2, 3, 5 . For example, 1, 2, 3, 4, 5, 6, 8, 9, 10, 12 is the sequence of the first 10 ugly numbers.
Note that 1 is typically treated as an ugly number, and n does not exceed 1690.
<Solution>263. Ugly Number 的衍生題
想法如下
c++
kotlin
- 所有的 ugly number 都是 2 or 3 or 5 的乘積
- ugly number 可以分解為下列三個 list
(1) 1x2，2x2，3x2，4x2......
(2) 1x3，2x3，3x3，4x3......
(3) 1x5，2x5，3x5，4x5......
- 下一個 ugly number 會是 min(L1*2, L2*3, L3*5)
- 綜合以上條件，可以推出在第 n 位的 ugly number 是多少
c++
kotlin
沒有留言:
張貼留言