Question (in Chinese): http://ac.jobdu.com/problem.php?pid=1373
Question Name: Number Of Ones
Question Description: Given an integer, find the number of 1s in the string representation of all integers from 0 to it.
Input: the input might contain multiple test cases. Each test case contains one single line, which includes two integers N and M (0 <= N, M <= 1000000000).
Output: For each test case, print the number of 1s in the string representation of all integers between N and M (both inclusive).
1 2 3 4 5 6 7 8 9 10 | Input: 0 5 1 13 21 55 31 99 Output: 1 6 4 7 |
The official solution converts the integers to string and then computes. While my solution deals with the integers directly.
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 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 | /*---------------------------------------------------------------- * Author: Sheng Yu codesays.com * Written: 08/31/2014 * Last updated: 08/31/2014 * * Filename: NumberOfOnes.java * Compilation: javac NumberOfOnes.java * Execution: java NumberOfOnes * JDK Used: 1.7 *----------------------------------------------------------------*/ import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.io.StreamTokenizer; /** * An utility to find the number of 1s, appears in the string representation * of all integers from 0 to a given integer. * @author Sheng Yu codesays.com */ public class NumberOfOnes { /** * Find the number of 1s in the string representation of all integers * from 0 to the given number. * @param number the original integer number * @return the number of 1s */ public int numberOfOnes(int number) { assert number >= 0; assert number <= 1000000000; // Handle the specific case. if (number == 0) return 0; // The number of digits in this number. int digits = (int) (Math.floor(Math.log10(number)) + 1); // The number of 1s in this number. int count = 0; // Make a copy of the input. int input = number; // In this round, the first digit of processing number. int firstDigit = 0; // In this round, the remaining part of processing number, // without the highest order digit. int remaining = 0; // In this round, the magnitude of the remaining part. // BEWARE of overflow. // 10 ** digits may overflow! int magnitude = (int) Math.pow(10, digits-1); // Process the number for the highest order digit to the lowest. for (int digit = digits; digit > 0; --digit) { // 1-based firstDigit = input / magnitude; remaining = input % magnitude; if (firstDigit == 0) { assert true; // Nope } else if (firstDigit == 1) { count += remaining + 1; // Do (magnitude / 10) firstly to avoid overflow. count += (magnitude / 10) * (digit -1); } else { count += magnitude; // Do (magnitude / 10) firstly to avoid overflow. count += (magnitude / 10) * firstDigit * (digit -1); } // Prepare for the next round. input = remaining; magnitude /= 10; } return count; } /** * Stub for test. * @param args the command line arguments. * @throws IOException when input gets error. */ public static void main(String[] args) throws IOException { StreamTokenizer st = new StreamTokenizer(new BufferedReader( new InputStreamReader(System.in))); int first, second, diff; NumberOfOnes counter = new NumberOfOnes(); while (st.nextToken() != StreamTokenizer.TT_EOF) { // Get the test case. first = (int) st.nval; st.nextToken(); second = (int) st.nval; // Make sure the first number is not smaller. if (first < second) { first ^= second; second ^= first; first ^= second; } diff = counter.numberOfOnes(first); if (second != 0) diff -= counter.numberOfOnes(second - 1); System.out.println(diff); } } } |