Statistics

Problem Statement for "KingdomAndPassword"

Problem Statement

King Dengklek has a special room protected by a password. The password is a positive integer that does not contain the digit zero. You are given the old password as a long oldPassword. King Dengklek has been using this password for a long time. Now, he wants to create a new password. You are also given a int[] restrictedDigits. The tradition in the kingdom insists that:

  • The digits in the new password are a permutation of the digits in oldPassword.
  • For each i, the i-th most significant digit (0-based index) of the new password is not restrictedDigits[i].

Return the new password X. If there are multiple solutions, return the one for which |oldPassword - X| is minimized. If there are still two possible solutions, return the smaller one. If there is no valid new password at all, return -1 instead.

Definition

Class:
KingdomAndPassword
Method:
newPassword
Parameters:
long, int[]
Returns:
long
Method signature:
long newPassword(long oldPassword, int[] restrictedDigits)
(be sure your method is public)

Notes

  • |x| denotes the absolute value of x. For example, |3| = |-3| = 3.
  • The new password may be equal to the old password (see example 2).

Constraints

  • oldPassword will be between 1 and 10^16 - 1, inclusive.
  • oldPassword will not contain the digit zero.
  • restrictedDigits will contain the same number of elements as the number of digits in oldPassword.
  • Each element of restrictedDigits will be between 1 and 9, inclusive.

Examples

  1. 548

    {5, 1, 8}

    Returns: 485

  2. 7777

    {4, 7, 4, 7}

    Returns: -1

    The only possible new password is 7777. Since digit 7 is restricted in two positions, this new password cannot be created.

  3. 58

    {4, 7}

    Returns: 58

  4. 172

    {4, 7, 4}

    Returns: 127

    Both 127 and 217 are valid passwords. No other valid password is closer to 172 than these two. In this situation, King Dengklek will choose the smaller one.

  5. 241529363573463

    {1, 4, 5, 7, 3, 9, 8, 1, 7, 6, 3, 2, 6, 4, 5}

    Returns: 239676554423331

  6. 172

    {1, 7, 2}

    Returns: 217

  7. 1

    {1}

    Returns: -1

  8. 9999999999999999

    {8, 3, 6, 6, 2, 1, 4, 6, 1, 2, 6, 5, 1, 7, 6, 7}

    Returns: 9999999999999999

  9. 9999999999999999

    {9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9}

    Returns: -1

  10. 6669982649

    {9, 6, 9, 4, 6, 6, 6, 9, 8, 2}

    Returns: 6826499669

  11. 2371232579661552

    {5, 5, 7, 6, 3, 7, 2, 1, 2, 3, 6, 2, 1, 5, 9, 2}

    Returns: 2369767555312221

  12. 4689479974398

    {7, 4, 3, 8, 9, 9, 6, 9, 8, 7, 4, 9, 4}

    Returns: 4689479899743

  13. 46128

    {2, 6, 1, 8, 4}

    Returns: 48216

  14. 64271513

    {5, 7, 6, 1, 2, 1, 3, 4}

    Returns: 64271513

  15. 9151

    {9, 1, 5, 1}

    Returns: 1915

  16. 23171

    {1, 7, 1, 3, 2}

    Returns: 23711

  17. 441462224

    {1, 4, 2, 2, 4, 4, 6, 4, 2}

    Returns: 426422414

  18. 1985196

    {9, 9, 8, 5, 6, 1, 1}

    Returns: 1899165

  19. 4338746596458

    {3, 4, 5, 6, 8, 8, 3, 6, 4, 7, 9, 4, 5}

    Returns: 4338746596458

  20. 66259

    {5, 6, 9, 2, 6}

    Returns: 65692

  21. 589326

    {3, 6, 9, 5, 8, 2}

    Returns: 586923

  22. 544823589767

    {3, 6, 2, 5, 4, 8, 5, 7, 9, 8, 7, 4}

    Returns: 544823657789

  23. 855313355

    {3, 3, 5, 5, 8, 5, 3, 1, 5}

    Returns: 853353551

  24. 7993235

    {9, 9, 3, 5, 3, 2, 7}

    Returns: 7599233

  25. 841689983651673

    {8, 3, 5, 9, 6, 3, 9, 8, 1, 8, 4, 1, 6, 6, 7}

    Returns: 799888666534311

  26. 6651564386

    {1, 5, 6, 8, 6, 5, 6, 3, 6, 4}

    Returns: 6651564638

  27. 7

    {7}

    Returns: -1

  28. 938394

    {9, 3, 3, 9, 4, 8}

    Returns: 899433

  29. 8433

    {3, 8, 3, 4}

    Returns: 8343

  30. 9356434931967561

    {9, 3, 5, 3, 4, 3, 1, 3, 4, 3, 5, 7, 6, 6, 9, 6}

    Returns: 7999666554433311

  31. 27799539

    {4, 1, 7, 7, 3, 6, 2, 9}

    Returns: 27935997

  32. 89994662991474

    {9, 6, 9, 7, 9, 2, 1, 8, 4, 6, 4, 9, 7, 9}

    Returns: 89796999642441

  33. 1395981945

    {4, 5, 5, 9, 1, 3, 5, 8, 9, 8}

    Returns: 1395981945

  34. 83

    {8, 4}

    Returns: 38

  35. 9735633893326

    {3, 1, 8, 5, 1, 7, 3, 6, 8, 5, 9, 9, 3}

    Returns: 9736235333689

  36. 568519

    {9, 5, 7, 1, 5, 6}

    Returns: 568519

  37. 578396383741221

    {3, 4, 8, 8, 7, 5, 3, 1, 6, 2, 8, 1, 3, 7, 7}

    Returns: 577988643332211

  38. 19793192822

    {4, 1, 5, 5, 9, 7, 2, 3, 3, 9, 1}

    Returns: 19793192822

  39. 811632227185915

    {1, 1, 2, 7, 5, 1, 4, 8, 3, 1, 6, 2, 5, 8, 9}

    Returns: 821112125356798

  40. 659

    {5, 8, 8}

    Returns: 659

  41. 54338445672426

    {8, 5, 4, 3, 6, 1, 2, 5, 4, 8, 6, 4, 4, 8}

    Returns: 54342234547686

  42. 64454

    {5, 4, 5, 3, 4}

    Returns: 46445

  43. 79637946132

    {3, 9, 2, 7, 7, 1, 7, 4, 2, 6, 8}

    Returns: 77996643321

  44. 4516632961524187

    {4, 3, 7, 8, 3, 1, 1, 5, 1, 5, 5, 9, 2, 4, 2, 4}

    Returns: 3987666454251211

  45. 8

    {8}

    Returns: -1

  46. 9868564685726583

    {2, 6, 5, 3, 3, 2, 2, 5, 1, 8, 6, 3, 4, 8, 8, 7}

    Returns: 9868564685726538

  47. 174

    {9, 1, 7}

    Returns: 174

  48. 91296294

    {2, 3, 9, 7, 2, 2, 9, 4}

    Returns: 91296429

  49. 766455314942

    {8, 6, 5, 6, 4, 3, 6, 2, 6, 5, 8, 4}

    Returns: 759566444321

  50. 78937768633

    {6, 5, 8, 3, 6, 5, 8, 7, 6, 5, 3}

    Returns: 78963336778

  51. 31588534453243

    {8, 6, 5, 5, 3, 5, 3, 4, 6, 8, 3, 5, 8, 4}

    Returns: 31488455542333

  52. 9962

    {9, 6, 6, 5}

    Returns: 6992

  53. 227187615844

    {6, 2, 1, 1, 9, 7, 9, 1, 4, 8, 4, 2}

    Returns: 218876752414

  54. 411

    {1, 2, 8}

    Returns: 411

  55. 6646113

    {9, 6, 1, 2, 1, 6, 3}

    Returns: 6466311

  56. 2952

    {2, 3, 5, 2}

    Returns: 5229

  57. 39659883423

    {5, 3, 6, 6, 7, 8, 3, 3, 5, 9, 5}

    Returns: 39598684332

  58. 483

    {5, 5, 2}

    Returns: 483

  59. 54

    {5, 1}

    Returns: 45

  60. 172

    {3, 7, 3}

    Returns: 127

  61. 132251342515551

    {4,5,5,5,5,5,2,5,3,5,1,5,4,5,5}

    Returns: 511112525253534

  62. 3345411115342361

    {4,1,1,3,1,1,1,6,2,1,4,1,1,1,1,1}

    Returns: 1651544114133332

  63. 1542545132141325

    {4,2,3,5,5,5,5,5,5,5,5,5,2,5,5,5}

    Returns: 5551111222335444

  64. 6119193531479171

    {8,1,8,1,1,1,1,6,4,1,1,2,7,1,1,1}

    Returns: 1919977116511433

  65. 6119193531479171

    {8,1,8,1,1,1,1,6,4,1,1,2,6,1,1,1}

    Returns: 1919977116511433

  66. 6118192831479171

    {8,1,8,1,1,1,1,6,4,1,1,2,6,1,1,1}

    Returns: 1919887117611432

  67. 6118192831579171

    {8,1,8,1,1,1,1,6,4,1,1,2,6,1,1,1}

    Returns: 1919887117611532

  68. 6118192831579171

    {1,1,8,1,1,1,1,6,4,1,1,2,6,1,1,1}

    Returns: -1

  69. 6118192831519771

    {1,1,5,1,1,1,1,9,4,1,1,2,6,1,1,1}

    Returns: -1

  70. 6119152831519771

    {1,1,5,1,1,1,1,4,4,1,1,2,6,1,1,1}

    Returns: -1

  71. 6119152833519771

    {1,1,5,1,1,1,1,4,4,1,1,1,6,1,1,1}

    Returns: -1

  72. 6119182833519771

    {1,1,5,1,1,1,1,4,4,1,1,1,6,1,1,1}

    Returns: -1

  73. 6119182833519741

    {8,1,5,1,1,1,1,4,4,1,1,1,6,1,1,1}

    Returns: 1919887116541332

  74. 6119182833519741

    {8,1,5,1,1,1,1,4,2,1,1,1,6,1,1,1}

    Returns: 1919887116541332

  75. 6919182833519741

    {8,1,1,1,1,1,1,4,4,1,1,1,6,1,1,1}

    Returns: 1999887116541332

  76. 5176858323464289

    {9,7,8,9,8,8,8,8,8,8,8,8,8,8,8,8}

    Returns: 8818223344556679

  77. 4752914625388618

    {9,8,7,3,8,8,8,8,8,8,8,8,8,8,8,8}

    Returns: 8188122344556679

  78. 241529363573463

    {1, 4, 5, 7, 3, 9, 8, 1, 7, 6, 3, 2, 6, 4, 5 }

    Returns: 239676554423331

  79. 548

    {5, 1, 8 }

    Returns: 485

  80. 9999912399945698

    {1, 4, 9, 9, 3, 9, 8, 1, 7, 6, 3, 2, 6, 4, 9, 8 }

    Returns: 9986959999994321

  81. 1234567899787

    {1, 2, 3, 4, 5, 6, 7, 8, 9, 9, 8, 7, 7 }

    Returns: 2143658777989

  82. 1234567891234567

    {2, 1, 1, 1, 1, 1, 1, 1, 1, 2, 1, 1, 1, 1, 1, 1 }

    Returns: 1234567891234567

  83. 123456781234567

    {9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9 }

    Returns: 123456781234567

  84. 123456789123451

    {1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 2 }

    Returns: -1

  85. 3941

    {5, 9, 5, 5 }

    Returns: 4139

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: