Question (in Chinese): http://ac.jobdu.com/problem.php?pid=1214
Question Name: Ugly Number
Question Description: Ugly numbers are the integers, whose prime factors could only be 2, 3, and/or 5. Typically 1 is also considered as an ugly number. We need to find the i(th) smallest ugly number.
Input: the input might contain multiple test cases. Each test case contains one line, which includes only one integer, to say i.
Output: For each test case, print the i(th) smallest ugly number.
1 2 3 4 5 6 | Input: 3 11 Output: 3 15 |
The solution is:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 | /*---------------------------------------------------------------- * Author: Sheng Yu - codesays.com * Written: 08/31/2014 * Last updated: 08/31/2014 * * Filename: UglyNumber.java * Compilation: javac UglyNumber.java * Execution: java UglyNumber * JDK Used: 1.7 *----------------------------------------------------------------*/ import java.util.ArrayList; import java.util.Arrays; import java.util.List; import java.util.Scanner; /** * An utility to get the i(th) ugly number. * Ugly number is the integer, whose prime factors can only be 1, 2, 3, and/or 5. * @author Sheng Yu - codesays.com */ public class UglyNumber { // The cache for computed ugly numbers. private static List<Integer> cache = new ArrayList<Integer>( Arrays.asList(1, 2, 3, 4, 5) ); // The indexes of three candidates to generate the next ugly number. // For example, next2 is the FIRST number, that next2 * 2 > currentMaxUglyNumber. private static int next2 = 2; private static int next3 = 1; private static int next5 = 1; /** * Find and return the i(th) ugly number. 1 is the first ugly number. * @param pos the pos(th) ugly number to return * @return the wanted ugly number */ public int getUglyNumber(int pos) { int nextUgly = 0; // Update the cache if necessary. while (pos > cache.size()) { // Get the next ugly number. nextUgly = Math.min(cache.get(next2) * 2, cache.get(next3) * 3); nextUgly = Math.min(nextUgly, cache.get(next5) * 5); cache.add(nextUgly); // Update the candidates to generate the next ugly number. while (cache.get(next2) * 2 <= nextUgly) next2 += 1; while (cache.get(next3) * 3 <= nextUgly) next3 += 1; while (cache.get(next5) * 5 <= nextUgly) next5 += 1; } return cache.get(pos-1); } /** * Stub for test. * @param args the command line arguments. */ public static void main(String[] args) { Scanner in = new Scanner(System.in); UglyNumber uglyNumber = new UglyNumber(); while (in.hasNextInt()) { System.out.println(uglyNumber.getUglyNumber(in.nextInt())); } } } |