> For the complete documentation index, see [llms.txt](https://netjimmy.gitbook.io/code-interview-note/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://netjimmy.gitbook.io/code-interview-note/array/ugly-number.md).

# Ugly Number

## 263 Ugly Number I

Check if a number is ugly number. Ugly numbers are positive numbers whose prime factors only include 2, 3, 5. 1 is usually consider as an ugly number.

```java
public boolean isUgly(int num) {
    int[] ugly = {2, 3, 5};
    for (int prime : ugly){
        while(num % prime == 0 && num > 0){
            num /= prime;
        }
    }
    return num == 1;
}
```

## 264 Ugly number II

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

* All the ugly numbers are in format 2^a x 3^b x 5^c, ugly numbers are subsequence factor of ugly numbers.
  1. Time O(n^2), Space O(1). Loop increasing number, check if it is a ugly number.
  2. Time O(n), Space O(n). Dynamic programming, Record the subsequence of prime factors and find the smallest.

```java
public int nthUglyNumber(int n) {
    int index_2 = 0, index_3 = 0, index_5 = 0; // the index on array
    int factor_2 = 1, factor_3 = 1, factor_5 = 1; // start with 1
    int[] arr = new int[n];
    int min = 1;

    for( int i = 0; i < n; i++){
        arr[i] = min;
        if (factor_2 == min) factor_2 = arr[index_2++] * 2;
        if (factor_3 == min) factor_3 = arr[index_3++] * 3;
        if (factor_5 == min) factor_5 = arr[index_5++] * 5;

        min = Math.min(factor_2, Math.min(factor_3, factor_5));
    }
    return arr[n-1];
}
```

## 313 Super ugly number

Write a program to find the nth super ugly number. Super ugly numbers are positive numbers whose all prime factors are in the given prime list primes of size k.

```java
public int nthSuperUglyNumber(int n, int[] primes) {
    int[] primes_idx = new int[primes.length];
    int[] primes_val = new int[primes.length];
    Arrays.fill(primes_val, 1);
    int[] ugly = new int[n];
    int min = 1;

    for (int i = 0; i < n; i++){
        ugly[i] = min;

        min = Integer.MAX_VALUE;
        for (int j = 0; j < primes.length; j++){

            if (primes_val[j] == ugly[i]) primes_val[j] = primes[j] * ugly[primes_idx[j]++];
            min = Math.min(min, primes_val[j]);
        }
    }
    return ugly[n-1];
}
```