Statistics

Problem Statement for "Passwords"

Problem Statement

A password is a sequence of alphanumeric characters. Count the number of different passwords of length N which contain at least L lowercase characters, at least U uppercase characters and at least D digits. Return this number modulo 1,000,000,009.

Definition

Class:
Passwords
Method:
countValid
Parameters:
int, int, int, int
Returns:
int
Method signature:
int countValid(int N, int L, int U, int D)
(be sure your method is public)

Constraints

  • N will be between 1 and 200,000, inclusive.
  • L will be between 0 and N, inclusive.
  • U will be between 0 and N, inclusive.
  • D will be between 0 and N, inclusive.

Examples

  1. 2

    0

    0

    2

    Returns: 100

    The only valid passwords are those consisting of digits only. There are 100 2-digit sequences.

  2. 3

    1

    1

    1

    Returns: 40560

    A valid password will contain exactly one lowercase and one uppercase letter and one digit. Since they can come in any order, there are 3!*26*26*10 = 40560 possible combinations.

  3. 4

    1

    1

    1

    Returns: 5029440

    This time, the exact number of characters of each type is undefined.

  4. 10

    1

    3

    3

    Returns: 818019214

  5. 5

    2

    2

    2

    Returns: 0

  6. 1

    0

    0

    0

    Returns: 62

  7. 1

    0

    0

    1

    Returns: 10

  8. 1

    1

    0

    0

    Returns: 26

  9. 1

    0

    1

    0

    Returns: 26

  10. 1

    1

    1

    0

    Returns: 0

  11. 2

    1

    1

    0

    Returns: 1352

  12. 2

    0

    1

    1

    Returns: 520

  13. 2

    1

    1

    1

    Returns: 0

  14. 3

    2

    0

    0

    Returns: 90584

  15. 3

    1

    1

    0

    Returns: 146016

  16. 3

    0

    0

    2

    Returns: 16600

  17. 8

    6

    0

    1

    Returns: 322631395

  18. 14

    14

    0

    0

    Returns: 707383878

  19. 200000

    100000

    1

    1

    Returns: 470373717

  20. 200000

    0

    0

    0

    Returns: 738150635

  21. 200000

    11

    111

    1111

    Returns: 298235838

  22. 200000

    199999

    0

    1

    Returns: 886429859

  23. 200000

    11414

    95127

    6

    Returns: 107223284

  24. 200000

    53263

    79521

    61833

    Returns: 940256784

  25. 200000

    33333

    34444

    41111

    Returns: 420445648

  26. 80106

    19152

    24734

    30681

    Returns: 504912396

  27. 101228

    71783

    18736

    4385

    Returns: 449664913

  28. 129244

    1

    1

    98687

    Returns: 20980021

  29. 89191

    81174

    2

    2

    Returns: 974129078

  30. 170436

    37064

    23234

    19240

    Returns: 776487996

  31. 156166

    8075

    42471

    10941

    Returns: 569158500

  32. 84705

    1980

    49267

    3041

    Returns: 323187298

  33. 53828

    8418

    2946

    37842

    Returns: 793891112

  34. 65776

    21706

    12290

    30546

    Returns: 897321747

  35. 84403

    3497

    1641

    55356

    Returns: 591245319

  36. 198645

    68610

    38232

    42110

    Returns: 663187821

  37. 100324

    85447

    65819

    86967

    Returns: 0

  38. 61647

    3844

    59389

    55274

    Returns: 0

  39. 112354

    4249

    5600

    14063

    Returns: 421824433

  40. 193320

    63309

    13467

    28097

    Returns: 28377419

  41. 33880

    3117

    935

    26425

    Returns: 197682457

  42. 105863

    60897

    33423

    955

    Returns: 949253849

  43. 17125

    3042

    5685

    3715

    Returns: 890687495

  44. 140891

    21685

    84401

    31220

    Returns: 595846236

  45. 50478

    16027

    2910

    7636

    Returns: 903804426

  46. 26263

    10974

    5978

    8107

    Returns: 65638354

  47. 192582

    8155

    111969

    12152

    Returns: 898909822

  48. 161034

    13729

    21241

    92858

    Returns: 785693515

  49. 107669

    9282

    29

    75233

    Returns: 41008220

  50. 43005

    36205

    2496

    2926

    Returns: 143495395

  51. 86280

    17645

    28201

    21975

    Returns: 115920085

  52. 40355

    6719

    8948

    8726

    Returns: 160933745

  53. 126850

    6318

    18871

    7645

    Returns: 443388831

  54. 142413

    6

    10

    136451

    Returns: 529678522

  55. 108616

    39814

    15183

    36002

    Returns: 12883772

  56. 199999

    31257

    25791

    61833

    Returns: 461562268

  57. 199999

    0

    0

    0

    Returns: 995776632

  58. 199999

    1

    1

    100000

    Returns: 73575300

  59. 199999

    35353

    35353

    35353

    Returns: 206155613

  60. 100000

    33333

    33333

    33333

    Returns: 397319698

  61. 111111

    2891

    25178

    25638

    Returns: 914512301

  62. 190000

    65000

    4

    7

    Returns: 908634905

  63. 199201

    0

    70000

    0

    Returns: 943311211

  64. 70000

    70000

    0

    0

    Returns: 373218645

  65. 162511

    14

    110

    8000

    Returns: 628798454

  66. 182512

    512

    512

    1024

    Returns: 896099224

  67. 170333

    333

    44101

    9000

    Returns: 132108256

  68. 200000

    1000

    1000

    1000

    Returns: 294300033

  69. 199999

    20000

    30000

    40000

    Returns: 548918749

  70. 200000

    20000

    20005

    30001

    Returns: 955047103

  71. 200000

    66030

    65465

    61111

    Returns: 782157891

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: