Statistics

Problem Statement for "DigitStringDiv1"

Problem Statement

You are given a digit string S and a positive integer X. We are going to erase some (possibly none, but not all) characters of S. While doing so, we have the following goals:

  • The string formed by the remaining characters (in their original order) cannot begin with the digit '0'.
  • When that string is converted to a number, its value must be strictly greater than the given X.

Two ways of erasing characters are different if there is an index i such that S[i] got erased in exactly one of the two ways.

Compute and return the number of ways in which we can erase some characters and achieve the goals stated above.

Definition

Class:
DigitStringDiv1
Method:
count
Parameters:
String, int
Returns:
long
Method signature:
long count(String S, int X)
(be sure your method is public)

Constraints

  • S will contain between 1 and 47 characters, inclusive.
  • Each character of S will be a digit ('0'-'9').
  • X will be between 0 and 777,444,111, inclusive.

Examples

  1. "0"

    1

    Returns: 0

  2. "101"

    9

    Returns: 3

    We can produce one of the strings "10", "11", and "101".

  3. "471"

    47

    Returns: 2

  4. "00000000000000000000000000000000000000000000000"

    777444111

    Returns: 0

  5. "99999999999999999999999999999999999999999999999"

    777444111

    Returns: 140737098539113

  6. "30358"

    169

    Returns: 12

  7. "88409"

    605

    Returns: 15

  8. "15496"

    366

    Returns: 10

  9. "95356"

    671

    Returns: 12

  10. "74558"

    149

    Returns: 16

  11. "30270300000006070000000000050000000004030700000"

    397910

    Returns: 98966780569119

  12. "75000908030900000040005000004010000400099099610"

    412711

    Returns: 108473978310664

  13. "00009523800000000800000000304000000010000009000"

    688341

    Returns: 8521750737601

  14. "00000000700500098000000060051400600039000000500"

    995136

    Returns: 312462571986

  15. "40000070000604000100700040090080400010001030060"

    798058

    Returns: 71511811003920

  16. "00026070060090000029040009770500006000096600660"

    949752

    Returns: 14448706015601

  17. "00082008908006700700500030090000970008027084086"

    688150

    Returns: 14100984527018

  18. "80040500390060130700000010009080000000800300000"

    284558

    Returns: 81800340040422

  19. "00079008074000105100400000070070003000808003800"

    967247

    Returns: 13956022845338

  20. "00002000020025087000000300202000020000000900615"

    986776

    Returns: 4564483638407

  21. "49569688890084365507736254513098816030118865010"

    0

    Returns: 140634140571130

  22. "0087705419306881478176502399462422212444792300"

    0

    Returns: 16475490353148

  23. "751876889653424817575110129720141503293946842"

    0

    Returns: 35184369957887

  24. "42877328236600405071997386416246946936987142827"

    88562286

    Returns: 140708665993708

  25. "44154891684500094538285430891944918610418874936"

    645385876

    Returns: 140705978173000

  26. "89284630051999320124485150300765438696922319726"

    127267548

    Returns: 139911417521678

  27. "42665033169989233749594221432871962303857411635"

    489120428

    Returns: 138537433619858

  28. "65656368448517177407122982356669080250865612805"

    529336722

    Returns: 140736577900844

  29. "74457205134905727426360932089187569090821345949"

    214206660

    Returns: 139620340123815

  30. "39174855848472663760459114227937609320514771498"

    672225710

    Returns: 140736167078345

  31. "82125869565424660479602281090474014492610821885"

    231922940

    Returns: 140735724193059

  32. "93738300067842630034940234672888059378692112768"

    205087562

    Returns: 138811386635176

  33. "21218823562940211258406314993179648559267366071"

    139166010

    Returns: 140728291998398

  34. "2222"

    97

    Returns: 5

    We have one way to produce the string "2222" and four ways to produce the string "222".

  35. "01928302938401293823583475787123093461230938400"

    421337666

    Returns: 69251155265696

  36. "2520020520520"

    592

    Returns: 7086

  37. "98"

    97

    Returns: 1

  38. "99999999999999999999999999999999999999999999999"

    0

    Returns: 140737488355327

  39. "740948824551711527614232216857618927954312"

    777439447

    Returns: 3847904874138

  40. "1111111111111111111111111111111111111111"

    11

    Returns: 1099511626955

  41. "313"

    322

    Returns: 0

  42. "10901445619183065529876219409617598034391052555"

    298341503

    Returns: 96751992112427

  43. "11111111111111111111111111111111111111111111111"

    111494777

    Returns: 140735735889968

  44. "4094882455171152761423221685"

    41

    Returns: 201326434

  45. "222293"

    88

    Returns: 43

  46. "01023124121433865876370989900101223876370989909"

    123456789

    Returns: 52776105373457

  47. "9432850420381576303002481261524389338910"

    502838

    Returns: 1089839520492

  48. "123456789"

    123

    Returns: 465

  49. "235"

    300

    Returns: 0

  50. "10901445619183065529876219409617598034391052555"

    0

    Returns: 96752727750623

  51. "481"

    47

    Returns: 3

  52. "106966673303425215124954723"

    0

    Returns: 100597759

  53. "01928302938401293823583475787123093461230938400"

    0

    Returns: 69252052664252

  54. "340881523246662904"

    4

    Returns: 229364

  55. "000000000"

    0

    Returns: 0

  56. "010"

    0

    Returns: 2

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: