Problem:
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.
Analysis:
This problem could be solved through a magic! The naive way to solve this problem is to count each ugly number we have scanned from 1. However, when the n gets larger and larger, it's more and more difficult to achieve such goal. We must find a more efficient way to solve this problem. Let us think in this way. Suppose we have already known the ugly sequenece(in ascending order). 1 2 3 4 5 6... At each position (number in the sequence), we have three choices to continue the sequence: multiple by 2, 3 or 5. Thus actually, the ugly sequence is actually the combiation of following sequences: sequence 2: 1*2 2*2 3*2 4*2 5*2 6*2 sequence 3: 1*3 2*3 3*3 4*3 5*3 6*3 sequence 5: 1*5 2*5 3*5 4*5 5*5 6*5 The ugly sequence is actually come from the merge of three sequence. Thus, we could use the skill of mering sorted list!!! Key: always pick the smallest one amongst those three lists. min = Math.min(ugly5, Math.min(ugly2, ugly3)); a[i] = min; The problem? Whether we need to write those three sequences first? No need, and we can not!!! Cause the ulgy sequence is the target we want to compute, we could no know them first!!! And we can always compute the a[i] from "a[ptr2] * 2", "a[ptr3] * 3" and "a[ptr5] * 5". And we know ptr2, ptr3, ptr5 must '<' than i. int ptr2 = 0, ptr3 = 0, ptr5 = 0; for (int i = 1; i < n; i++) 'i' start from 1, ptr start from 0. we calculate the a[i] based on a[j] (j<i). This is inherently a dynamic programming problem. Right? Since sequence 2, sequence 3, and sequence 5 only differ in the multiplier, we have no need to record them. Just pretend they ar exist. ugly2 = a[ptr2] * 2; ugly3 = a[ptr3] * 3; ugly5 = a[ptr5] * 5; Acoording to the pattern of merging lists, we just need to update the current pointer for each list is enough!!!
Solution:
public class Solution { public int nthUglyNumber(int n) { int[] a = new int[n]; a[0] = 1; int ptr2 = 0, ptr3 = 0, ptr5 = 0; int ugly2, ugly3, ugly5, min; for (int i = 1; i < n; i++) { ugly2 = a[ptr2] * 2; ugly3 = a[ptr3] * 3; ugly5 = a[ptr5] * 5; min = Math.min(ugly5, Math.min(ugly2, ugly3)); a[i] = min; if (min == ugly2) ptr2++; if (min == ugly3) ptr3++; if (min == ugly5) ptr5++; } return a[n-1]; } }