Statistics

Problem Statement for "QuickCount"

Problem Statement

Here is an algorithm for counting quickly: instead of saying a number, simply say the rightmost non-zero digit of that number. So for example, 13700 becomes just 7 (assuming you are counting in base 10).

Given two base-10 integers, first and last, as well as a number base, numBase, return a int[] containing the number of times you would say each digit if you were to count from first to last in base numBase. The int[] should contain exactly (numBase - 1) elements; the first element is the number of times you say the digit 1, the second element is how many times you say the digit 2, etc.

Definition

Class:
QuickCount
Method:
howMany
Parameters:
int, int, int
Returns:
int[]
Method signature:
int[] howMany(int first, int last, int numBase)
(be sure your method is public)

Constraints

  • first will be between 1 and 2000000000, inclusive.
  • last will be between 1 and 2000000000, inclusive.
  • first will be less than or equal to last.
  • numBase will be between 2 and 10, inclusive.

Examples

  1. 1

    9

    10

    Returns: { 1, 1, 1, 1, 1, 1, 1, 1, 1 }

    Each digit from 1 to 9 is said exactly once.

  2. 1

    20

    10

    Returns: { 3, 3, 2, 2, 2, 2, 2, 2, 2 }

    The numbers 1 through 9 correspond to the digits 1 through 9, respectively. The numbers 11 through 19 correspond to the digits 1 through 9, respectively. The number 10 becomes the digit 1, and the number 20 becomes the digit 2. In total, digits 1 and 2 are said three times each, and all other digits are said twice.

  3. 16

    31

    4

    Returns: { 6, 5, 5 }

    The counting is now being done in base four. Here is 16 through 31 in base four (note that this table uses HTML, and will not look correct with plaintext plugins): 1610 = 1004 � � � � � � � � 2010 = 1104 � � � � � � � � 2410 = 1204 � � � � � � � � 2810 = 1304 1710 = 1014 � � � � � � � � 2110 = 1114 � � � � � � � � 2510 = 1214 � � � � � � � � 2910 = 1314 1810 = 1024 � � � � � � � � 2210 = 1124 � � � � � � � � 2610 = 1224 � � � � � � � � 3010 = 1324 1910 = 1034 � � � � � � � � 2310 = 1134 � � � � � � � � 2710 = 1234 � � � � � � � � 3110 = 1334 The base four numbers 100, 101, 110, 111, 121, and 131 will all become the digit 1. The numbers 102, 112, 120, 122, and 132 will become the digit 2. The numbers 103, 113, 123, 130, and 133 will become the digit 3. Therefore, the digit 1 will be said 6 times, and the digits 2 and 3 will be said 5 times each.�

  4. 1

    2000000000

    2

    Returns: { 2000000000 }

    In base 2, everything will be spoken using the digit '1', since every positive number is a series of only zeroes and ones when converted to binary.

  5. 1

    1

    2

    Returns: { 1 }

  6. 65123

    684135

    8

    Returns: { 88430, 88431, 88431, 88431, 88430, 88430, 88430 }

  7. 1235

    6494

    3

    Returns: { 2630, 2630 }

  8. 73

    100

    10

    Returns: { 3, 2, 3, 3, 3, 3, 3, 4, 4 }

  9. 8

    8

    3

    Returns: { 0, 1 }

  10. 1

    1

    10

    Returns: { 1, 0, 0, 0, 0, 0, 0, 0, 0 }

  11. 1

    4

    4

    Returns: { 2, 1, 1 }

  12. 5

    36

    7

    Returns: { 6, 5, 5, 5, 6, 5 }

  13. 9561

    1035942

    3

    Returns: { 513191, 513191 }

  14. 123

    123456789

    5

    Returns: { 30864171, 30864167, 30864165, 30864164 }

  15. 86

    456

    6

    Returns: { 73, 74, 75, 75, 74 }

  16. 1

    1000000000

    9

    Returns: { 125000004, 125000002, 125000000, 125000000, 125000000, 124999999, 124999998, 124999997 }

  17. 1230949760

    1638533832

    8

    Returns: { 58226297, 58226297, 58226297, 58226296, 58226295, 58226295, 58226296 }

  18. 286797048

    637129665

    10

    Returns: { 38925848, 38925847, 38925847, 38925846, 38925847, 38925846, 38925844, 38925846, 38925847 }

  19. 967888833

    1139638067

    6

    Returns: { 34349845, 34349848, 34349847, 34349846, 34349849 }

  20. 498550654

    1755530954

    7

    Returns: { 209496717, 209496718, 209496717, 209496717, 209496716, 209496716 }

  21. 1021167637

    1224423171

    7

    Returns: { 33875923, 33875923, 33875921, 33875923, 33875923, 33875922 }

  22. 277574540

    1338137032

    8

    Returns: { 151508927, 151508926, 151508928, 151508929, 151508928, 151508927, 151508928 }

  23. 68821550

    500162602

    6

    Returns: { 86268213, 86268212, 86268211, 86268209, 86268208 }

  24. 545850516

    1478377462

    10

    Returns: { 103614106, 103614106, 103614105, 103614104, 103614103, 103614108, 103614107, 103614104, 103614104 }

  25. 592215897

    663133861

    10

    Returns: { 7879775, 7879774, 7879776, 7879773, 7879773, 7879775, 7879773, 7879773, 7879773 }

  26. 459369184

    1192655445

    2

    Returns: { 733286262 }

  27. 457729460

    1036075593

    9

    Returns: { 72293266, 72293269, 72293268, 72293267, 72293266, 72293265, 72293266, 72293267 }

  28. 95152498

    516528369

    10

    Returns: { 46819542, 46819542, 46819542, 46819541, 46819542, 46819542, 46819540, 46819541, 46819540 }

  29. 161745907

    176711799

    3

    Returns: { 7482947, 7482946 }

  30. 580594064

    1330445648

    9

    Returns: { 93731448, 93731447, 93731446, 93731446, 93731449, 93731449, 93731450, 93731450 }

  31. 1224208475

    1697087766

    3

    Returns: { 236439647, 236439645 }

  32. 3

    1999999997

    2

    Returns: { 1999999995 }

  33. 3

    1999999997

    3

    Returns: { 1000000002, 999999993 }

  34. 3

    1999999997

    4

    Returns: { 666666669, 666666663, 666666663 }

  35. 3

    1999999997

    5

    Returns: { 500000000, 499999999, 499999999, 499999997 }

  36. 3

    1999999997

    6

    Returns: { 400000002, 400000001, 399999999, 399999997, 399999996 }

  37. 3

    1999999997

    7

    Returns: { 333333336, 333333334, 333333334, 333333331, 333333331, 333333329 }

  38. 3

    1999999997

    8

    Returns: { 285714289, 285714285, 285714286, 285714285, 285714285, 285714283, 285714282 }

  39. 3

    1999999997

    9

    Returns: { 250000004, 250000000, 250000001, 250000000, 249999999, 249999997, 249999997, 249999997 }

  40. 3

    1999999997

    10

    Returns: { 222222222, 222222221, 222222222, 222222222, 222222222, 222222222, 222222222, 222222221, 222222221 }

  41. 50

    80

    9

    Returns: { 3, 3, 3, 3, 4, 5, 5, 5 }

  42. 2

    2000000000

    10

    Returns: { 222222222, 222222223, 222222222, 222222222, 222222222, 222222222, 222222222, 222222222, 222222222 }

  43. 1

    2000000000

    3

    Returns: { 1000000004, 999999996 }

  44. 1

    2000000000

    10

    Returns: { 222222223, 222222223, 222222222, 222222222, 222222222, 222222222, 222222222, 222222222, 222222222 }

  45. 16

    31

    10

    Returns: { 2, 2, 2, 1, 1, 2, 2, 2, 2 }

  46. 1

    2000000000

    8

    Returns: { 285714290, 285714287, 285714286, 285714285, 285714285, 285714284, 285714283 }

  47. 1

    11111111

    10

    Returns: { 1234575, 1234567, 1234567, 1234567, 1234567, 1234567, 1234567, 1234567, 1234567 }

  48. 1

    1

    2

    Returns: { 1 }

  49. 13

    1999999385

    9

    Returns: { 249999926, 249999924, 249999924, 249999922, 249999920, 249999919, 249999919, 249999919 }

  50. 1

    2000000000

    2

    Returns: { 2000000000 }

  51. 31

    31

    5

    Returns: { 1, 0, 0, 0 }

  52. 1

    9

    10

    Returns: { 1, 1, 1, 1, 1, 1, 1, 1, 1 }

  53. 8160741

    1971901242

    7

    Returns: { 327290084, 327290084, 327290084, 327290083, 327290083, 327290084 }

  54. 1

    1999999999

    9

    Returns: { 250000006, 250000002, 250000001, 250000000, 249999999, 249999997, 249999997, 249999997 }

  55. 1231

    1981815667

    7

    Returns: { 330302409, 330302406, 330302406, 330302406, 330302405, 330302405 }

  56. 533

    52523

    4

    Returns: { 17330, 17331, 17330 }

This problem statement is the exclusive and proprietary property of TopCoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of TopCoder, Inc. is strictly prohibited. (c)2024, TopCoder, Inc. All rights reserved.
This problem was used for: