Statistics

Problem Statement for "PermutationCounter"

Problem Statement

You have a group of non-zero digits, which are not necessarily unique. If you can insert '0' digits wherever you wish, there are an infinite number of integers which have exactly those non-zero digits. For example, given the group of digits {1, 2}, you can create the numbers 12, 21, 102, 120, 201, 210, 1002, 1020, etc. Given a potentially large number n in String format, return how many numbers that use the same exact non-zero digits are less than it. Leading zeros are not allowed.

Definition

Class:
PermutationCounter
Method:
count
Parameters:
String
Returns:
long
Method signature:
long count(String n)
(be sure your method is public)

Constraints

  • n will have between 1 and 50 characters, inclusive.
  • n will consist only of digit characters ('0' - '9').
  • n will not start with a '0'.
  • There will be at most 2^63 - 1 integers with the same non-zero digits as n that are less than n

Examples

  1. "1020"

    Returns: 7

    From the problem statement above, we see that there are 7 values less than the given value.

  2. "50000000000000"

    Returns: 13

    Since there is only one non-zero digit in this number, the only way to increment the number is by inserting a zero after the 5. Therefore, the sequence is: 5, 50, 500, 5000, ..., 50000000000000.

  3. "1030000040000"

    Returns: 1414

  4. "10101010101010101010101010101010101010101010101010"

    Returns: 84859704298201

  5. "98765432109876543210"

    Returns: 2360008843617599

  6. "9999988888777776666655555444"

    Returns: 2042129794477893119

  7. "1901712530271201432987123"

    Returns: 141588146596382454

  8. "6202528111465188657739980"

    Returns: 9199969922561799023

  9. "754706171577635805626571261"

    Returns: 9221263653163756851

  10. "50"

    Returns: 1

  11. "907082051609750"

    Returns: 1228293023

  12. "59100250045245"

    Returns: 34583442

  13. "473004850000970439460030"

    Returns: 201544492776877

  14. "3680384070896"

    Returns: 13484031

  15. "500360511010643"

    Returns: 168627869

  16. "20327559000296885090040"

    Returns: 547823994771227

  17. "7398700"

    Returns: 719

  18. "10100801000038"

    Returns: 118116

  19. "20"

    Returns: 1

  20. "521080600800000000011300700695"

    Returns: 12131588882550723

  21. "2010006530"

    Returns: 19007

  22. "190103000577000"

    Returns: 5357451

  23. "896340019040041352050004164"

    Returns: 2411274400627896724

  24. "5640590684220610030096210"

    Returns: 117728755582225319

  25. "890486052230449607"

    Returns: 2439009581504

  26. "400000"

    Returns: 5

  27. "2006480554300805091606330"

    Returns: 19998330793650341

  28. "4000005517097570160"

    Returns: 22061183631

  29. "4339"

    Returns: 6

  30. "8703020701340"

    Returns: 12855669

  31. "8"

    Returns: 0

  32. "97600084700002000098"

    Returns: 7477059451

  33. "3050183570209753020008800796"

    Returns: 7881016280742567603

  34. "280326680001247001674630121"

    Returns: 5333558791440143509

  35. "68000250"

    Returns: 1443

  36. "8902031"

    Returns: 2113

  37. "5"

    Returns: 0

  38. "9096010070341920160180406"

    Returns: 22856761370892710

  39. "40"

    Returns: 1

  40. "500049740092"

    Returns: 668347

  41. "300810804080044760256000006204"

    Returns: 1010175649689803276

  42. "849802103306606069009"

    Returns: 14412450156335

  43. "66101990710008147"

    Returns: 10259838558

  44. "3009800"

    Returns: 131

  45. "940900"

    Returns: 54

  46. "480036902046097075040402006"

    Returns: 153943280562342707

  47. "702003590447097925008409"

    Returns: 3030591666746774

  48. "900"

    Returns: 2

  49. "6380549070000005040333100220"

    Returns: 225248017678034372

  50. "28203209730"

    Returns: 277883

  51. "60715150"

    Returns: 3945

  52. "800005666"

    Returns: 2240

  53. "4000029461700530109018005"

    Returns: 5192206038834273

  54. "9177"

    Returns: 9

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: