Statistics

Problem Statement for "TheLockDivOne"

Problem Statement

John is obsessed with security. Recently he bought a new electronic lock. It is protected by a password containing n digits, where each digit is either zero or one. John decides to change the password every day. On the first day, the password is all zeroes. On each day that follows, he will select one or more digits that all have the same value and change their values (so zeroes become ones, and ones become zeroes). He must select the digits according to the following rules:

  1. During the first 2^n days, he must never use the same password twice.
  2. Each new password must come as early as possible alphabetically while not violating rule 1.

For example, if n is 2, the password on the first day is "00". The next day, he can change one or both 0's to get "01", "10" or "11". Of these possibilities, "01" comes earliest alphabetically. The next day, he can change either the 0 or the 1 to get "11" or "00". He can't choose "00" because it was already used, so he chooses "11". The next day, he can change one or both 1's to get "10", "01" or "00". He has already used "01" and "00", so he must choose "10".

Given ints n and k, return the password that comes latest alphabetically during the first k days.

Definition

Class:
TheLockDivOne
Method:
password
Parameters:
int, long
Returns:
String
Method signature:
String password(int n, long k)
(be sure your method is public)

Notes

  • If A and B are two Strings of the same length, then A comes earlier alphabetically than B if it contains a smaller character at the first position where the Strings differ.

Constraints

  • n will be between 1 and 50, inclusive.
  • k will be between 1 and 2^n, inclusive.

Examples

  1. 2

    4

    Returns: "11"

    This is the example from the statement. The password sequence is the following - "00", "01", "11", "10".

  2. 3

    8

    Returns: "111"

    "000", "001", "011", "010", "110", "100", "101", "111".

  3. 4

    6

    Returns: "0110"

  4. 10

    1

    Returns: "0000000000"

  5. 10

    597

    Returns: "1111111001"

  6. 10

    15

    Returns: "0000001111"

  7. 10

    621

    Returns: "1111111001"

  8. 8

    249

    Returns: "11111110"

  9. 7

    117

    Returns: "1111110"

  10. 9

    442

    Returns: "111111011"

  11. 8

    228

    Returns: "11111110"

  12. 1

    1

    Returns: "0"

  13. 5

    15

    Returns: "01111"

  14. 5

    13

    Returns: "01111"

  15. 1

    1

    Returns: "0"

  16. 1

    1

    Returns: "0"

  17. 6

    32

    Returns: "011111"

  18. 10

    512

    Returns: "0111111111"

  19. 7

    64

    Returns: "0111111"

  20. 8

    128

    Returns: "01111111"

  21. 4

    8

    Returns: "0111"

  22. 2

    2

    Returns: "01"

  23. 3

    4

    Returns: "011"

  24. 10

    513

    Returns: "1111111001"

  25. 10

    513

    Returns: "1111111001"

  26. 6

    33

    Returns: "111100"

  27. 5

    17

    Returns: "11101"

  28. 10

    1024

    Returns: "1111111111"

  29. 7

    128

    Returns: "1111111"

  30. 7

    128

    Returns: "1111111"

  31. 10

    1024

    Returns: "1111111111"

  32. 10

    1

    Returns: "0000000000"

  33. 48

    208512386748577

    Returns: "111111111111111111111111111111111111111111010100"

  34. 25

    27411233

    Returns: "1111111111111111111101110"

  35. 38

    105246396407

    Returns: "01111111111111111111111111111111100001"

  36. 23

    6621849

    Returns: "11111111111111111101101"

  37. 45

    11398125475641

    Returns: "011111111111111111111111111111111111111011000"

  38. 23

    6380913

    Returns: "11111111111111111101101"

  39. 34

    3005954651

    Returns: "0011111111111111111111111111100100"

  40. 50

    1052937316880545

    Returns: "11111111111111111111111111111111111111111111010110"

  41. 50

    75288321082145

    Returns: "00011111111111111111111111111111111111111111010101"

  42. 50

    174927595212791

    Returns: "00111111111111111111111111111111111111111111010100"

  43. 50

    282406622136985

    Returns: "01111111111111111111111111111111111111111111010110"

  44. 50

    562949953421312

    Returns: "01111111111111111111111111111111111111111111111111"

  45. 50

    1125899906842624

    Returns: "11111111111111111111111111111111111111111111111111"

  46. 50

    562949953421313

    Returns: "11111111111111111111111111111111111111111111010010"

  47. 50

    1

    Returns: "00000000000000000000000000000000000000000000000000"

  48. 34

    2719886102

    Returns: "0011111111111111111111111111100100"

  49. 31

    41952292

    Returns: "0000011111111111111111111101011"

  50. 32

    19008497

    Returns: "00000001111111111111111111101010"

  51. 49

    93536637109166

    Returns: "0011111111111111111111111111111111111111111010101"

  52. 7

    100

    Returns: "1111110"

  53. 50

    725899906842624

    Returns: "11111111111111111111111111111111111111111111010010"

  54. 50

    123456789012345

    Returns: "00011111111111111111111111111111111111111111011111"

  55. 50

    1025899906842619

    Returns: "11111111111111111111111111111111111111111111010110"

  56. 50

    543797347268423

    Returns: "01111111111111111111111111111111111111111111010111"

  57. 50

    281474976710657

    Returns: "01111111111111111111111111111111111111111111010110"

  58. 50

    33553333

    Returns: "00000000000000000000000001111111111111111111111111"

  59. 50

    562949953131313

    Returns: "01111111111111111111111111111111111111111111111101"

  60. 49

    3214659873999

    Returns: "0000000111111111111111111111111111111111111011011"

  61. 50

    140737488355328

    Returns: "00011111111111111111111111111111111111111111111111"

  62. 50

    100000000000000

    Returns: "00011111111111111111111111111111111111111111010101"

  63. 50

    1234565676543

    Returns: "00000000011111111111111111111111111111111111011010"

  64. 50

    1000000000000000

    Returns: "11111111111111111111111111111111111111111111010110"

  65. 49

    562946180435304

    Returns: "1111111111111111111111111111111111111111111111100"

  66. 50

    562949953421666

    Returns: "11111111111111111111111111111111111111111111010010"

  67. 20

    513

    Returns: "00000000001111111001"

  68. 50

    365487745125434

    Returns: "01111111111111111111111111111111111111111111010110"

  69. 50

    27

    Returns: "00000000000000000000000000000000000000000000011111"

  70. 50

    1125899871101813

    Returns: "11111111111111111111111111111111111111111111111100"

  71. 49

    35184372088832

    Returns: "0000111111111111111111111111111111111111111111111"

  72. 50

    745493936856584

    Returns: "11111111111111111111111111111111111111111111010010"

  73. 20

    1025

    Returns: "00000000011111111000"

  74. 49

    562949953421000

    Returns: "1111111111111111111111111111111111111111111111111"

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: