Question (in Chinese): http://ac.jobdu.com/problem.php?pid=1515

Question Name: Print One To Max Of N Digits

Question Description: Give an integer N, generate and print all the integers from 1 to (10^N – 1).

Input: an integer.

Output: the integers from 1 to (10^N – 1).

1 2 3 4 5 6 7 8 9 10 11 12 | Input: 1 Output: 1 2 3 4 5 6 7 8 9 |

The solution:

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 62 63 64 65 66 67 68 69 | /** * Filename : Print1ToMaxOfNDigits.java * Dependency: None * Author : Sheng Yu (codesays.com) * Create at : 2014-08-07 * JDK used : 1.7 * Change log: None */ import java.util.Scanner; public class Print1ToMaxOfNDigits { /** * Print the integers with 1 to N digits. * @param digits: the maximum digits in the output integers. */ public void show(int digits) { // Build cache for output. StringBuilder outCache = new StringBuilder(); int printCount = 500; // Print every 500 records. int currentCount = 0; // Find enough space to store the maximum number. StringBuilder numbers = new StringBuilder(String.format("%0" + digits + "d", 0)); int currentMaxDigit = digits - 1; int currentDigit = digits - 1; int temp = 0; // Increase the numbers by one each round. while (currentMaxDigit >= 0) { // Increase the numbers by one each round. currentDigit = digits - 1; while (currentMaxDigit >= 0) { temp = numbers.charAt(currentDigit) - '0'; if (temp < 9) { // No carry after the adding in this digit. Finish computing. numbers.setCharAt(currentDigit, Character.forDigit(temp+1, 10)); break; } else { // There is carry after adding here. Need to continue the computing. numbers.setCharAt(currentDigit, '0'); currentDigit -= 1; if (currentDigit < currentMaxDigit) currentMaxDigit -= 1; } } if (currentMaxDigit >= 0) { // Catch the output and pint them. outCache.append(numbers.substring(currentMaxDigit) + "n"); currentCount += 1; if (currentCount == printCount) { // Cache is full. Print out the content and clear the cache. currentCount = 0; System.out.print(outCache); outCache.setLength(0); } } } // Maybe some content is still waiting for printing. if (currentCount != 0) System.out.println(outCache); return; } /** * Stub for testing. * @param args */ public static void main(String[] args) { Scanner sin = new Scanner(System.in); Print1ToMaxOfNDigits printer = new Print1ToMaxOfNDigits(); int digits = sin.nextInt(); printer.show(digits); } } |