# Ugly Number

## Question

Ugly number is a number that only have factors 3, 5 and 7.

Design an algorithm to find the Kth ugly number.
The first 5 ugly numbers are 3, 5, 7, 9, 15 ...

Example
If K=4, return 9.
Challenge
O(K log K) or O(K) time.


## 题解1 - TLE

Lintcode 和 Leetcode 中质数稍微有点区别，这里以 Lintcode 上的版本为例进行说明。寻找第 K 个丑数，丑数在这里的定义是仅能被3，5，7整除。简单粗暴的方法就是挨个检查正整数，数到第 K 个丑数时即停止。

### Java

class Solution {
/**
* @param k: The number k.
* @return: The kth prime number as description.
*/
if (k <= 0) return -1;

int count = 0;
long num = 1;
while (count < k) {
num++;
if (isUgly(num)) {
count++;
}
}

return num;
}

private boolean isUgly(long num) {
while (num % 3 == 0) {
num /= 3;
}
while (num % 5 == 0) {
num /= 5;
}
while (num % 7 == 0) {
num /= 7;
}

return num == 1;
}
}


## 题解2 - 二分查找

### C++

class Solution {
public:
/*
* @param k: The number k.
* @return: The kth prime number as description.
*/
if (k <= 0) return -1;

vector<long long> ugly(k + 1);
ugly[0] = 1;
int index = 0, index3 = 0, index5 = 0, index7 = 0;
while (index <= k) {
long long val = ugly[index3]*3 < ugly[index5]*5 ? ugly[index3]*3 : ugly[index5]*5;
val = val < ugly[index7]*7 ? val : ugly[index7]*7;
if (val == ugly[index3]*3) ++index3;
if (val == ugly[index5]*5) ++index5;
if (val == ugly[index7]*7) ++index7;
ugly[++index] = val;
}
return ugly[k];
}
};


### Java

class Solution {
/**
* @param k: The number k.
* @return: The kth prime number as description.
*/
if (k <= 0) return -1;

ArrayList<Long> nums = new ArrayList<Long>();
for (int i = 0; i < k; i++) {
long minNextUgly = Math.min(nextUgly(nums, 3), nextUgly(nums, 5));
minNextUgly = Math.min(minNextUgly, nextUgly(nums, 7));
}

return nums.get(nums.size() - 1);
}

private long nextUgly(ArrayList<Long> nums, int factor) {
int size = nums.size();
int start = 0, end = size - 1;
while (start + 1 < end) {
int mid = start + (end - start) / 2;
if (nums.get(mid) * factor > nums.get(size - 1)) {
end = mid;
} else {
start = mid;
}
}
if (nums.get(start) * factor > nums.get(size - 1)) {
return nums.get(start) * factor;
}

return nums.get(end) * factor;
}
}


### Golang

var uglyNum []int

func init() {
uglyNum = append(uglyNum, 1)
len := 1
i, j, k := 0, 0, 0
for uglyNum[len-1] < math.MaxInt32 {
tmpMin := min(uglyNum[i]*2, uglyNum[j]*3, uglyNum[k]*5)
uglyNum = append(uglyNum, tmpMin)
len++

if uglyNum[i]*2 == tmpMin {
i++
}
if uglyNum[j]*3 == tmpMin {
j++
}
if uglyNum[k]*5 == tmpMin {
k++
}
}
}

func min(a, b, c int) int {
tmp := a
if b < tmp {
tmp = b
}
if c < tmp {
tmp = c
}
return tmp
}

func nthUglyNumber(n int) int {
if n < 1 {
return 1
}
return uglyNum[n-1]
}


### 源码分析

nextUgly根据输入的丑数数组和 factor 决定下一个丑数，nums.add(1L)中1后面需要加 L表示 Long, 否则编译错误。

TBD