Statistics

Problem Statement for "PageNumbers"

Problem Statement

We have a book with N pages, numbered 1 to N. How many times does each digit occur in the page numbers?

You are given an int N. Return a int[] with 10 elements, where for all i between 0 and 9, inclusive, the element i will be the number of times digit i occurs when we write down all the numbers between 1 and N, inclusive.

Definition

Class:
PageNumbers
Method:
getCounts
Parameters:
int
Returns:
int[]
Method signature:
int[] getCounts(int N)
(be sure your method is public)

Notes

  • You may assume that for any valid input each of the output values fits into an int.

Constraints

  • N will be between 1 and 1,000,000,000, inclusive.

Examples

  1. 7

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

    The page numbers in this case are simply 1, 2, 3, 4, 5, 6, and 7.

  2. 11

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

    In comparison to the previous case, we added the pages 8, 9, 10, and 11. Now we have each digit exactly once, except for the digit 1 that occurs four times: once in 1 and 10, and twice in 11.

  3. 19

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

    Digits 2 to 9 now occur twice each, and we have plenty of occurrences of the digit 1.

  4. 999

    Returns: {189, 300, 300, 300, 300, 300, 300, 300, 300, 300 }

    Due to symmetry, each of the digits 1 to 9 occurs equally many times in the sequence 1,2,...,999.

  5. 1

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

  6. 10

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

  7. 789012

    Returns: {384614, 495705, 495702, 495701, 495701, 495701, 495701, 484714, 394714, 384714 }

  8. 900000000

    Returns: {708888897, 820000000, 820000000, 820000000, 820000000, 820000000, 820000000, 820000000, 820000000, 720000001 }

  9. 1000000000

    Returns: {788888898, 900000001, 900000000, 900000000, 900000000, 900000000, 900000000, 900000000, 900000000, 900000000 }

  10. 987654321

    Returns: {780521262, 891632373, 891632364, 891632284, 891631584, 891625584, 891575584, 891175584, 888175584, 868175584 }

  11. 504050403

    Returns: {396420286, 503430181, 503430181, 503430181, 502480488, 406470888, 402420080, 402420080, 402420080, 402420080 }

  12. 799940036

    Returns: {628864977, 739976014, 739976014, 739976011, 739966041, 739966004, 739966004, 739906040, 639966003, 639786114 }

  13. 2

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

  14. 9

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

  15. 999999998

    Returns: {788888889, 900000000, 900000000, 900000000, 900000000, 900000000, 900000000, 900000000, 900000000, 899999991 }

  16. 9

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

  17. 98

    Returns: {9, 20, 20, 20, 20, 20, 20, 20, 20, 18 }

  18. 987

    Returns: {188, 299, 299, 299, 299, 299, 299, 299, 296, 276 }

  19. 9876

    Returns: {2867, 3978, 3978, 3978, 3978, 3978, 3978, 3974, 3944, 3744 }

  20. 98765

    Returns: {38546, 49657, 49657, 49657, 49657, 49657, 49652, 49612, 49312, 47312 }

  21. 987654

    Returns: {484225, 595336, 595336, 595336, 595336, 595330, 595280, 594880, 591880, 571880 }

  22. 9876543

    Returns: {5829904, 6941015, 6941015, 6941015, 6941008, 6940948, 6940448, 6936448, 6906448, 6706448 }

  23. 98765432

    Returns: {68175583, 79286694, 79286694, 79286686, 79286616, 79286016, 79281016, 79241016, 78941016, 76941016 }

  24. 987654321

    Returns: {780521262, 891632373, 891632364, 891632284, 891631584, 891625584, 891575584, 891175584, 888175584, 868175584 }

  25. 12

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

  26. 123

    Returns: {22, 57, 27, 23, 22, 22, 22, 22, 22, 22 }

  27. 1234

    Returns: {343, 689, 389, 349, 344, 343, 343, 343, 343, 343 }

  28. 12345

    Returns: {4664, 8121, 5121, 4721, 4671, 4665, 4664, 4664, 4664, 4664 }

  29. 123456

    Returns: {58985, 93553, 63553, 59553, 59053, 58993, 58986, 58985, 58985, 58985 }

  30. 1234567

    Returns: {713306, 1058985, 758985, 718985, 713985, 713385, 713315, 713307, 713306, 713306 }

  31. 12345678

    Returns: {8367627, 11824417, 8824417, 8424417, 8374417, 8368417, 8367717, 8367637, 8367628, 8367627 }

  32. 123456789

    Returns: {96021948, 130589849, 100589849, 96589849, 96089849, 96029849, 96022849, 96022049, 96021959, 96021949 }

  33. 78

    Returns: {7, 18, 18, 18, 18, 18, 18, 17, 8, 7 }

  34. 789

    Returns: {148, 259, 259, 259, 259, 259, 259, 249, 159, 149 }

  35. 7890

    Returns: {2269, 3379, 3379, 3379, 3379, 3379, 3379, 3270, 2370, 2270 }

  36. 78901

    Returns: {30572, 41681, 41680, 41680, 41680, 41680, 41680, 40582, 31582, 30582 }

  37. 789012

    Returns: {384614, 495705, 495702, 495701, 495701, 495701, 495701, 484714, 394714, 384714 }

  38. 7890123

    Returns: {4635146, 5746057, 5746027, 5746023, 5746022, 5746022, 5746022, 5636146, 4736146, 4636146 }

  39. 181843383

    Returns: {137016968, 229814847, 147128079, 147127447, 147120362, 147116978, 147116978, 147116978, 138903740, 137016968 }

  40. 351689177

    Returns: {275934727, 386734994, 386045738, 337734916, 286045738, 277734916, 276034916, 275945736, 275944905, 275934905 }

  41. 355799137

    Returns: {278388723, 389499772, 389499734, 345298870, 289499724, 285098000, 278499724, 278498862, 278399723, 278397999 }

  42. 294320736

    Returns: {225557880, 336668254, 330979728, 236578988, 235878981, 235558244, 235558244, 235558180, 235558143, 229878880 }

  43. 775798184

    Returns: {612388428, 723499524, 723499439, 723499439, 723499439, 723297623, 722499438, 694093993, 612398618, 612396613 }

  44. 53062443

    Returns: {36787128, 47835795, 47835239, 46897239, 46834732, 39897128, 36827128, 36824684, 36824684, 36824684 }

  45. 289926179

    Returns: {221859827, 332970918, 322893198, 232960838, 232960838, 232960838, 232960018, 232959838, 232886008, 222812188 }

  46. 69638993

    Returns: {47714589, 58825700, 58825700, 58824694, 58815699, 58815699, 58393687, 48715699, 48715693, 48353681 }

  47. 876990153

    Returns: {693085179, 804196090, 804196036, 804196036, 804196035, 804196029, 804186179, 800186179, 770186179, 693176333 }

  48. 534002179

    Returns: {423294987, 534401718, 534400818, 528402818, 523402818, 457402818, 423400638, 423400638, 423400628, 423400628 }

  49. 279699325

    Returns: {214738762, 325849873, 305549195, 225849789, 225849763, 225849763, 225849088, 225449088, 215749762, 215447740 }

  50. 584724752

    Returns: {458759345, 569870456, 569865209, 569860455, 569584961, 553584201, 468859445, 468784151, 463484098, 458759345 }

  51. 480283054

    Returns: {375415915, 486243916, 486226971, 486142971, 466425971, 386142910, 386142905, 386142905, 376419015, 376132905 }

  52. 68027845

    Returns: {46738110, 57821375, 57819221, 57811375, 57811371, 57811365, 55839210, 47811210, 46838156, 46810264 }

  53. 718798808

    Returns: {572188559, 682098470, 673299661, 673299661, 673299661, 673299661, 673299661, 592097279, 572998188, 572197369 }

  54. 989674322

    Returns: {781729262, 892840373, 892840366, 892840285, 892839585, 892839262, 892813585, 892733585, 892403585, 872077908 }

  55. 168988445

    Returns: {127284484, 207384041, 138395595, 138395595, 138395537, 138395485, 137383930, 128395484, 128381822, 127372930 }

  56. 157223945

    Returns: {119309084, 187644141, 130338087, 130310141, 130309191, 127533131, 120309184, 119533130, 119309184, 119309130 }

  57. 844260816

    Returns: {670523978, 781634269, 781595079, 781534262, 775055896, 770534262, 770525079, 770524261, 714784995, 670524161 }

  58. 132666273

    Returns: {102525847, 146303232, 113303206, 105303132, 102636857, 102636857, 102598679, 102525851, 102525847, 102525847 }

  59. 212103960

    Returns: {168245047, 271360118, 180460118, 168252157, 168251196, 168251196, 168251187, 168251186, 168251186, 168251147 }

  60. 616789681

    Returns: {490984828, 598885621, 592095938, 592095938, 592095938, 592095938, 508675284, 491085520, 490995512, 490985510 }

  61. 455709962

    Returns: {358352849, 469453997, 469453997, 469453996, 425163959, 364873922, 358453989, 358363949, 358353986, 358353912 }

  62. 996166768

    Returns: {786675946, 897753826, 897687057, 897687057, 897687057, 897687057, 896850363, 896676016, 896675947, 889009484 }

  63. 348177247

    Returns: {272880144, 383968503, 383891203, 332068403, 282068401, 273891145, 273891145, 273887641, 273057392, 272880144 }

  64. 645851371

    Returns: {511420367, 622530850, 622530477, 622530449, 618381749, 612373121, 557371749, 511520369, 511471739, 511420367 }

  65. 150081565

    Returns: {114095538, 175124649, 125042517, 125042517, 125042517, 115124049, 115042412, 115042406, 115033972, 115032406 }

  66. 345718229

    Returns: {271356442, 382465783, 382457483, 328175673, 278175673, 272175673, 271457443, 271375673, 271356673, 271356443 }

  67. 274413817

    Returns: {211605061, 322709988, 297119980, 222705980, 222032798, 221605162, 221605162, 216018980, 211605079, 211605061 }

  68. 112984251

    Returns: {88683245, 105762860, 89778559, 88794255, 88793507, 88793247, 88793245, 88793245, 88787497, 88767497 }

  69. 634156299

    Returns: {503471849, 614539260, 614482960, 608639160, 603639160, 603479160, 537628460, 503471860, 503471860, 503471860 }

  70. 252487219

    Returns: {196434141, 307545252, 259519602, 206545142, 206532362, 198932362, 196445142, 196444362, 196441362, 196434142 }

  71. 223771813

    Returns: {176178461, 287289380, 204832190, 177060376, 176288561, 176288561, 176288561, 176252189, 176178475, 176178461 }

  72. 513374784

    Returns: {408979348, 513465244, 510090459, 509440029, 508990244, 422364243, 408989458, 408984228, 408979353, 408979348 }

  73. 729805259

    Returns: {579796805, 690902656, 690707876, 680902556, 680902556, 680901816, 680901546, 610706806, 580806806, 580606806 }

  74. 146797122

    Returns: {111988122, 169896279, 123099126, 123099122, 119896245, 113099122, 112896245, 112095368, 111998122, 111995245 }

  75. 301733977

    Returns: {232697065, 341808176, 341074198, 242802132, 241063198, 241063198, 241063198, 240997174, 240963187, 240963165 }

  76. 222128495

    Returns: {175260489, 286300096, 199655584, 175261600, 175261596, 175261500, 175261499, 175261499, 175260995, 175260495 }

  77. 469143440

    Returns: {367466984, 478521535, 478478094, 478477535, 447613908, 378466984, 377610425, 368466984, 368466984, 367610425 }

  78. 136809860

    Returns: {105002727, 152913837, 116103976, 112913837, 106103976, 106103976, 105913828, 105103966, 105013788, 105003727 }

  79. 379494403

    Returns: {294637274, 405748381, 405748381, 385242785, 305742092, 305647280, 305647280, 305141684, 295647280, 295136088 }

  80. 662318406

    Returns: {523356477, 634465988, 633775988, 633375988, 633357488, 633357481, 587994295, 523357480, 523356887, 523356480 }

  81. 283338429

    Returns: {217964482, 329075593, 312414023, 228350873, 227965513, 227965483, 227965483, 227965483, 221303343, 217964483 }

  82. 339087456

    Returns: {266421642, 377445296, 377445296, 315620210, 267445253, 267445193, 267445186, 267444642, 267441642, 266521642 }

  83. 80758297

    Returns: {56130747, 66483560, 66483558, 66483460, 66483460, 66481758, 66473460, 66431758, 57131055, 56372457 }

  84. 171247758

    Returns: {129718245, 211324874, 139777115, 139729356, 139727115, 139719355, 139719346, 130966823, 129718246, 129718245 }

  85. 435496250

    Returns: {344237845, 455348955, 455348906, 450845106, 380841357, 344745097, 344248096, 344247845, 344247845, 344244096 }

  86. 558476863

    Returns: {440029966, 551141077, 551141077, 551141077, 551117940, 507994804, 441040934, 441036930, 440506894, 440029966 }

  87. 980168283

    Returns: {775244732, 886155843, 886087543, 886087459, 886087458, 886087458, 886085742, 886077458, 876245020, 856244732 }

  88. 81368131

    Returns: {56776423, 67255598, 66887433, 66855557, 66787423, 66787423, 66785555, 66777423, 58144687, 56776423 }

  89. 543212345

    Returns: {429904664, 541008121, 540917467, 540117067, 533117017, 473117011, 429904664, 429904664, 429904664, 429904664 }

    Watch out for the time limit.

  90. 543212347

    Returns: {429904664, 541008123, 540917471, 540117071, 533117021, 473117013, 429904665, 429904665, 429904664, 429904664 }

  91. 901101010

    Returns: {711742234, 820752335, 820650301, 820650301, 820650301, 820650301, 820650301, 820650301, 820650301, 721751312 }

  92. 736583768

    Returns: {584883046, 695994157, 695994157, 692577695, 685993157, 685976926, 685476925, 621476885, 584886816, 584883046 }

  93. 100100

    Returns: {39213, 50122, 50020, 50020, 50020, 50020, 50020, 50020, 50020, 50020 }

  94. 898245765

    Returns: {707917646, 819028757, 818974523, 818928757, 818924523, 818918523, 818917752, 818917712, 816409178, 716163412 }

  95. 979865789

    Returns: {774825648, 885936759, 885936759, 885936759, 885936759, 885936549, 885931549, 885791539, 875891449, 855557229 }

  96. 956806542

    Returns: {758998447, 870103015, 870103015, 870103014, 870103007, 866909490, 859908990, 859101904, 859008447, 815808447 }

  97. 909123892

    Returns: {724582962, 826494073, 826464073, 826460072, 826459179, 826459179, 826459179, 826459179, 826459172, 734706858 }

  98. 999999978

    Returns: {788888887, 899999998, 899999998, 899999998, 899999998, 899999998, 899999998, 899999997, 899999988, 899999840 }

  99. 911204569

    Returns: {727695876, 829211557, 827706987, 827702417, 827701987, 827701387, 827701317, 827701307, 827701307, 738905877 }

  100. 789456826

    Returns: {621621962, 732733073, 732733070, 732733063, 732689890, 732629890, 732622890, 722078889, 632078816, 622078789 }

  101. 800673017

    Returns: {630674855, 740439910, 740439902, 740438920, 740438902, 740438902, 740411920, 740331920, 641001919, 640328901 }

  102. 999999999

    Returns: {788888889, 900000000, 900000000, 900000000, 900000000, 900000000, 900000000, 900000000, 900000000, 900000000 }

  103. 567859765

    Returns: {446622846, 557733957, 557733957, 557733957, 557733957, 525593489, 455583718, 447583678, 446683612, 446623612 }

  104. 897411603

    Returns: {707404414, 818506729, 818504521, 818504521, 818416124, 818404520, 818404424, 817816024, 814816024, 714816024 }

  105. 100000001

    Returns: {68888904, 80000003, 80000000, 80000000, 80000000, 80000000, 80000000, 80000000, 80000000, 80000000 }

  106. 796995991

    Returns: {627087689, 738198800, 738198799, 738198799, 738198799, 738198791, 738193791, 734193791, 637197799, 634185759 }

  107. 923878347

    Returns: {736230464, 847341575, 841219923, 837219871, 836341473, 836341465, 836341465, 836339813, 836309160, 760108812 }

  108. 819760940

    Returns: {652774125, 763645235, 753884294, 753884294, 753884285, 753884284, 753875225, 753835225, 673535225, 653535166 }

  109. 999996666

    Returns: {788887926, 899999037, 899999037, 899999037, 899999037, 899999037, 899998668, 899997926, 899997926, 899981261 }

  110. 999999888

    Returns: {788888868, 899999979, 899999979, 899999979, 899999979, 899999979, 899999979, 899999979, 899999967, 899999202 }

  111. 100000000

    Returns: {68888897, 80000001, 80000000, 80000000, 80000000, 80000000, 80000000, 80000000, 80000000, 80000000 }

  112. 100

    Returns: {11, 21, 20, 20, 20, 20, 20, 20, 20, 20 }

  113. 109700801

    Returns: {85441558, 96551063, 86850260, 86850260, 86850260, 86850260, 86850260, 86751062, 86750162, 86450962 }

  114. 999999001

    Returns: {788888594, 899999701, 899999700, 899999700, 899999700, 899999700, 899999700, 899999700, 899999700, 899993712 }

  115. 901000260

    Returns: {711490090, 820600417, 820600117, 820600056, 820600056, 820600056, 820600047, 820600046, 820600046, 721600307 }

  116. 1001

    Returns: {194, 303, 300, 300, 300, 300, 300, 300, 300, 300 }

  117. 101

    Returns: {12, 23, 20, 20, 20, 20, 20, 20, 20, 20 }

  118. 103

    Returns: {14, 25, 21, 21, 20, 20, 20, 20, 20, 20 }

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: