Statistics

Problem Statement for "NumberGameAgain"

Problem Statement

In this problem, you are going to play a simple number game. The rules of the game are as follows:

  • You have a single variable called x. Initially, x is set to 1.
  • In each step, you can change the value of x either to 2x or to 2x+1.
  • You are given a list of forbidden values. If at any moment your x is on the list, you lose the game.
  • You are also given a target value y. If at any moment your x is equal to y, you win the game. (Note that the previous item applies sooner: if y is forbidden, you lose the game when you reach it.)
  • If at any moment winning the game becomes impossible, you lose the game.

For example, assume that the forbidden values are 4 and 7, and the goal is 12. You can win the game as follows: change x from 1 to 2*1+1=3, then from 3 to 2*3=6, and then from 6 to 2*6=12.

You are given a long[] table. The elements of table are the forbidden values.

You are also given a int k. Consider all possible goals y between 2 and (2^k)-1, inclusive. For how many of these goals is it possible to win the game? Compute and return the answer to that question.

Definition

Class:
NumberGameAgain
Method:
solve
Parameters:
int, long[]
Returns:
long
Method signature:
long solve(int k, long[] table)
(be sure your method is public)

Constraints

  • k will be between 2 and 40, inclusive.
  • The number of elements in table will be between 0 and 20, inclusive.
  • all numbers in table will be between 2 and 2^k - 1, inclusive.
  • all numbers in table will be distinct.

Examples

  1. 3

    {2,4,6}

    Returns: 2

    There are three forbidden values: 2, 4, and 6. As k=3, we are considering y between 2 and (2^3)-1 = 7. This is how the game would end for each of these y's: For y=2 we cannot win the game because 2 is forbidden. For y=3 we can win the game: we change x from 1 to 3. For y=4 we cannot win the game because 4 is forbidden. For y=5 we cannot win the game. We would need to change x from 1 to 2 and then from 2 to 5, but we cannot do that because 2 is forbidden. For y=6 we cannot win the game because 6 is forbidden. For y=7 we can win the game: we change x from 1 to 3, and then from 3 to 7. Thus, within the specified range there are two values of y for which we can win the game.

  2. 5

    {2,3}

    Returns: 0

    In this case, we will always reach a forbidden value after the very first step of the game. Therefore, there is no y for which we can win the game.

  3. 5

    {}

    Returns: 30

    With no forbidden values we can win this game for any y between 2 and 31, inclusive.

  4. 40

    {2,4,8,16,32141531,2324577,1099511627775,2222222222,33333333333,4444444444,2135}

    Returns: 549755748288

  5. 40

    {}

    Returns: 1099511627774

  6. 20

    {88,138390,363924,18595,148,179170,29,490195,28,67,533,980413,1033224,227290,652478,786172,27,5,768}

    Returns: 561093

  7. 21

    {382020,1445653,31,29,300,821043,1608648,938706,993,328,303126,803567,1635671,181113,448,9,23992,16,128,18}

    Returns: 1425251

  8. 22

    {456,1369504,22,1023,29,759570,3120819,21,1369469,31,2899250,898,10,77851,392,518634,2720592,1208313,2066001}

    Returns: 2842555

  9. 23

    {7414275,968,700,7569021,4636021,7457149,6474984,9,16,753,6399929,1506380,28,5276549,2789774,17,11,4666917,50}

    Returns: 4423680

  10. 24

    {6,11148196,753,16536446,15105497,22,17,12845893,11,1800903,3048265,13615059,558,27,107,89,8888988,3992069,8510101,12}

    Returns: 9437173

  11. 25

    {486649,365,31018949,21,13,29742539,13053525,6218302,681,12233394,22689231,322,101,721,27090548,29,3482263,2,8638823}

    Returns: 9961469

  12. 26

    {54209036,38543038,885,13479317,11723476,6,884,22,40619945,37776795,60676905,865,45484517,30770176,945,60919240,30,498,29,26}

    Returns: 37486590

  13. 27

    {47247981,831,6,130035091,651,949,13,100928445,153,46518102,919,12,80584190,43432245,35800307,11760202,90992231,41436662}

    Returns: 98828259

  14. 28

    {373,31260440,97482257,188776065,185063003,831,4,68263201,26,9,737,68650298,235235276,628,6,228047431,749,189364347,146861366}

    Returns: 132120557

  15. 29

    {439,805,18829969,516379994,190119985,301,308343015,457150673,54538296,850,528316617,14,437734769,506,233431462,32,21,18890252,2}

    Returns: 195035118

  16. 30

    {32,292641136,188591956,959,346577409,100425583,1063890011,19,15,143179048,69839892,701,875,1016444246,490849697,658,805230500,5,22,301}

    Returns: 562036713

  17. 31

    {1988471706,446218215,1368866320,3,666725002,464686744,28,893,1950958221,54,1561233216,204,1341564121,470,249,877678913,1117960589}

    Returns: 1073741816

  18. 32

    {27,1072051022,728,926,1989237896,5,1708948442,1071886677,3500713120,405325248,26,229,1975422774,3536496306,10,3,860,18,3552626203,153849953}

    Returns: 805306369

  19. 33

    {5058030095,570755421,8037734191,41850318,185,603,2324911949,8585272262,5,25,812,7942103333,15,831,482,10,6514706797,4063273821,2462894324,7}

    Returns: 3741318892

  20. 34

    {14815453878,1956970307,3374326207,855,31,591,13895214614,2941883265,1253311279,23,813,291,758,18,14270394763,3161712096,13021508155,12027487392,17,13}

    Returns: 10703863780

  21. 35

    {442,10683828955,19296611249,7034648448,2,25540676691,3,436,1598291679,32274583693,27964470680,828,701,19964411242,28,5959774712,15,547,24,14855588983}

    Returns: 0

  22. 36

    {33597674427,9,42472360205,68027669140,610,13547457550,46887167983,18122267782,45630577447,40299889254,199,198,6,11,19,316,36405003400,481,57356373097,29}

    Returns: 29796335609

  23. 37

    {8,44432292276,19786425719,735,14,172,41303192740,629,32,636,22739836803,13,293,134936667183,7436989460,114385790088,105276048037,62894185703,3,115424383614}

    Returns: 49123688433

  24. 38

    {216821968208,265303441442,108632847731,215391636152,48858748997,346,92873523452,160,25,26,236367519280,815,21,27004204921,124190431584,261845849867,31,454,595}

    Returns: 202400333816

  25. 39

    {8,229,80685624233,342218712995,495654491884,520606867795,105449832776,34167844968,797,501415898147,497619358731,102349138155,30,34625516022,12,110,22,982,800,9}

    Returns: 261993005020

  26. 40

    {214,949534855192,401465371895,769455154386,204436229945,1072519053599,193530069243,17,1008,101068968091,449581977219,187,133,14,745,382208539203,716563162403}

    Returns: 863288426459

  27. 40

    {1048576,2097152,4194305,8388611,16777223,33554446,67108893,134217786,268435572,536871145,1073742291,2147484583,4294969167,8589938335,17179876670,34359753340,68719506681,137439013362,274878026724,549756053448}

    Returns: 1099510579199

  28. 40

    {1048576,2097152,4194305,8388611,16777223,33554446,67108892,134217785,268435571,536871142,1073742285,2147484571,4294969142,8589938285,17179876571,34359753142,68719506285,137439012571,274878025142,549756050285}

    Returns: 1099510579199

  29. 40

    {1048576,2097152,4194304,8388609,16777218,33554437,67108874,134217748,268435497,536870994,1073741988,2147483977,4294967954,8589935908,17179871817,34359743635,68719487270,137438974540,274877949081,549755898163}

    Returns: 1099510579199

  30. 40

    {1048576,2097153,4194306,8388613,16777226,33554452,67108905,134217810,268435621,536871242,1073742485,2147484970,4294969941,8589939882,17179879765,34359759530,68719519061,137439038122,274878076244,549756152489}

    Returns: 1099510579199

  31. 40

    {1048576,2097152,4194304,8388608,16777217,33554434,67108868,134217737,268435474,536870948,1073741897,2147483794,4294967589,8589935179,17179870358,34359740717,68719481435,137438962870,274877925741,549755851483}

    Returns: 1099510579199

  32. 40

    {1048576,2097152,4194304,8388609,16777218,33554437,67108875,134217750,268435501,536871003,1073742006,2147484013,4294968026,8589936053,17179872106,34359744212,68719488424,137438976849,274877953698,549755907397}

    Returns: 1099510579199

  33. 40

    {1048576,2097153,4194307,8388615,16777230,33554461,67108923,134217846,268435692,536871384,1073742769,2147485539,4294971078,8589942156,17179884313,34359768626,68719537253,137439074506,274878149012,549756298024}

    Returns: 1099510579199

  34. 40

    {1048576,2097152,4194305,8388610,16777220,33554441,67108882,134217764,268435528,536871056,1073742113,2147484226,4294968452,8589936905,17179873811,34359747622,68719495244,137438990488,274877980977,549755961954}

    Returns: 1099510579199

  35. 40

    {1048576,2097153,4194307,8388615,16777230,33554460,67108921,134217843,268435687,536871374,1073742749,2147485498,4294970997,8589941994,17179883988,34359767977,68719535955,137439071910,274878143820,549756287641}

    Returns: 1099510579199

  36. 40

    {1048576,2097152,4194304,8388608,16777217,33554435,67108871,134217743,268435486,536870972,1073741944,2147483889,4294967779,8589935559,17179871119,34359742239,68719484479,137438968958,274877937917,549755875834}

    Returns: 1099510579199

  37. 4

    {8,9,10,11,12,13,15,14}

    Returns: 6

  38. 2

    {}

    Returns: 2

  39. 4

    {2,3}

    Returns: 0

  40. 2

    {3}

    Returns: 1

  41. 3

    {2,3}

    Returns: 0

  42. 5

    {4,9}

    Returns: 23

  43. 5

    {9,4}

    Returns: 23

  44. 40

    {2, 4, 8, 16, 32141531, 2324577, 1099511627775, 2222222222, 33333333333, 4444444444, 2135 }

    Returns: 549755748288

  45. 40

    {10000000000 }

    Returns: 1099511627647

  46. 3

    {2, 4, 6 }

    Returns: 2

  47. 40

    {34359738366, 68719476734, 137438953470 }

    Returns: 1099511627665

  48. 40

    { }

    Returns: 1099511627774

  49. 5

    {12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31 }

    Returns: 10

  50. 40

    {1099511627772 }

    Returns: 1099511627773

  51. 40

    {2, 3 }

    Returns: 0

  52. 40

    {1000000, 10000000, 1073741854 }

    Returns: 1099509398529

  53. 40

    {6832473984, 91372849234 }

    Returns: 1099511627504

  54. 40

    {2, 14 }

    Returns: 412316860416

  55. 40

    {10123, 2434, 345243, 1231234, 452345, 3456, 34, 643, 63, 2, 2345, 1231 }

    Returns: 514855010306

  56. 40

    {549755813888, 2, 3 }

    Returns: 0

  57. 40

    {2, 4, 6 }

    Returns: 274877906944

  58. 5

    {2, 4, 8, 16 }

    Returns: 15

  59. 5

    {16, 8, 4, 2 }

    Returns: 15

  60. 30

    {2, 7 }

    Returns: 268435456

  61. 40

    {2, 5, 7, 13 }

    Returns: 137438953473

  62. 4

    {2, 4, 8 }

    Returns: 7

  63. 39

    {34, 56, 2, 5 }

    Returns: 257698037760

  64. 10

    {2 }

    Returns: 511

  65. 4

    {8, 9, 4 }

    Returns: 11

  66. 40

    {1099511627771 }

    Returns: 1099511627773

  67. 40

    {1099511627774 }

    Returns: 1099511627773

  68. 40

    {100000000000 }

    Returns: 1099511627759

  69. 40

    {137058, 2659878, 45698732 }

    Returns: 1099502682113

  70. 5

    {2, 10, 8, 15 }

    Returns: 12

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: