Statistics

Problem Statement for "ORSolitaireDiv2"

Problem Statement

Note that the memory limit for all tasks in this SRM is 256 MB.

This problem statement contains subscripts that may not display properly if viewed outside of the applet.

Manao is playing a solitaire game called OR-solitaire. In this game, the player starts with a number X = 0 and should obtain the number goal in one or more moves. The set of valid moves is determined by a int[] numbers. In each move, the player chooses some element of numbers and replaces X with the bitwise OR of X and the chosen element.

Fox Ciel wants Manao to stop playing OR-solitaire and move on with his life. She decided to erase some of the elements from numbers in such a way that it becomes impossible to complete the game. Return the minimum number of elements that need to be removed to achieve this.

Definition

Class:
ORSolitaireDiv2
Method:
getMinimum
Parameters:
int[], int
Returns:
int
Method signature:
int getMinimum(int[] numbers, int goal)
(be sure your method is public)

Notes

  • If a and b are single bits then a | b is defined as max(a, b). For two integers, A and B, in order to calculate A | B, they need to be represented in binary: A = (an...a1)2, B = (bn...b1)2 (if the lengths of their representations are different, the shorter one is prepended with the necessary number of leading zeroes). Then A | B = C = (cn...c1)2, where ci = ai | bi. For example, 10 | 3 = (1010)2 | (0011)2 = (1011)2 = 11.

Constraints

  • numbers will contain between 1 and 20 elements, inclusive.
  • Each element of numbers will be between 1 and 1,000,000,000.
  • The elements in numbers will be distinct.
  • goal will be between 1 and 1,000,000,000.

Examples

  1. {1, 2, 4}

    7

    Returns: 1

    The goal of the game is to obtain X = 7 from X = 0. The possible moves are to replace X with bitwise OR of X and 1, bitwise OR of X and 2 and bitwise OR of X and 4. X = 7 can be obtained only by using each of the three moves at least once, so removing any single element from numbers will make the game impossible to finish.

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

    7

    Returns: 2

    In this example, Fox Ciel should remove the number 7 and one of the numbers 1, 2, 4.

  3. {12571295, 2174218, 2015120}

    1

    Returns: 0

    There is no need to remove elements from numbers, since the game cannot be completed in its initial version.

  4. {5, 2, 4, 52, 62, 9, 8, 3, 1, 11, 6}

    11

    Returns: 3

  5. {109127425,391193886,77568450,481751837,411889236,488364804,480598915,7490879,95057181,16530444,55580676,92339390,273649157,5737290,144995698,480240667,402927632,95353526,170311435,485081164}

    536870911

    Returns: 4

  6. {27,2,26,7,21,29,28,31,5,6,18,12,15,30,14,17,24,16,9,10}

    31

    Returns: 9

  7. {55,691,650,432,160,720,290,732,903,723,785,79,294,345,453,964,897,253,690,113}

    1023

    Returns: 5

  8. {22528,20912,22320,16401,22784,23955,18352,1315,23569,20250,2363,19608,6584,5411,1467,2601,4499,21792,6170,1680}

    24507

    Returns: 5

  9. {823447732,593423634,809515236,555028692,861241348,307814628,51914944,592246884,826888400,716806243,33560704,559253716,313595780,489421707,860106944,382793666}

    861796596

    Returns: 4

  10. {172034615,172296301,134293593,888499515,155460170,337462,46305587,139101223,488570356,151333909,172230716,229655861,933046747,441405556,267718708,493313234,151259174,16787519,138413121,54788182}

    189083263

    Returns: 3

  11. {744207802,459506930,96031044,94305333,71623564,401261714,143654920,180838023,426804418,292454963,396375937,783935062,983980901,302100998}

    751841480

    Returns: 0

  12. {335643795,18915408,335545345,38248827,67215425,270540866,276958948,335610067,388882431,285245507,667758452,352396432,270540930,2203715,337682562,268443840,9808608}

    354526419

    Returns: 3

  13. {828679106,142753985,468167304,136484418,424919616,325098545,12669632,29376579,151062080,6427202,25416387,29425667}

    165926595

    Returns: 2

  14. {14696720,564142160,12623892,153215056,683712604,559980552,679510340,123160,10485840,29417556,16793624,673243408,689995776,702636316,18964496,153124864,562044948}

    702669148

    Returns: 4

  15. {532700295,225353158,352321581,83887104,335544361,1033,279970861,278921221,231758666,276824065,287309832,295699493,286261252,196315035}

    363856941

    Returns: 2

  16. {899600840,656757270,755007825,686528173,268726219,559245235,611788458,368346758,17334298,549641380,83919197,389157370,605061982,813127881}

    756581215

    Returns: 1

  17. {76185604,90374409,299926793,299892748,13141252,50463749,34111501,62948621,96503053,20972548,344621325,321487884,384401417,35717381,281182217,102760452,348225793}

    401310989

    Returns: 5

  18. {442637816,365993835,833768101,224044145,27693200,53501952,736425935,498092463,17969284,329547920,301994112}

    330756244

    Returns: 1

  19. {157548768,809931613,134482024,89129000,154403976,220202152,202376288,90178592,896745400,67372192,151259176,136580160,136577120}

    225709288

    Returns: 3

  20. {270937159,976111677,307477007,942809093,177199459,940703749,1321286,1179907,538976325,270540804,406192130,1179666,806489093,482799521,8514}

    943074647

    Returns: 1

  21. {331620352,468879139,558315151,332793348,270686573,545367314,222433724,16908804,26092552,37757964,8521224,123346056}

    333325836

    Returns: 1

  22. {282901120,545260432,609183355,480548122,805306513,16793873,295699345,396053269,553648768,824771288,276840465}

    832594833

    Returns: 0

  23. {273359450,289947800,273170536,80220416,25187170,92500880,281244176,71659778,352539266,29696920,289746968,336204706,352522848,72221170,83981112}

    365917178

    Returns: 4

  24. {138575997,13140277,2359423,134774887,614668282,376463334,145359177,6291735,2359644,112698510,524315,11272501}

    149848447

    Returns: 2

  25. {706800612,539625532,641828790,911986104,782645710,651888112,567875154,296932750,150522789,784806895,861099181,793599418,583494227}

    568022875

    Returns: 0

  26. {873489428,183416836,933225247,605773996,339951784,537673864,864546674,878190600,622414902,289669712,507675130,273440940,71600834,218965105,717092117,459351570,863958917,907127289}

    878666940

    Returns: 1

  27. {787106,794824393,432498940,4524672,327714,880834007,1903234,134745250,135531552,135857314,289655489,355873959,293353013,515665780,1116192,265218,5573120,810183189}

    140316322

    Returns: 2

  28. {201523612,255746029,37142548,303185926,9437188,36700208,268582944,304529458,278265856,36077600,304496662,303169574,3424262,42074132,43434020,896243228,41959440}

    313966646

    Returns: 4

  29. {999211135,433773221,482044170,820097540,184977891,730109131,815883022,106991648,309415701,617840716,70343733,775278463}

    376296895

    Returns: 0

  30. {551021845,833724846,708342593,13216,413501017,281113001,431828254,110335187,884874972,404005282}

    420983730

    Returns: 0

  31. {1851520,5899553,80888865,13649313,9831456,9700481,77070496,80495616,77480353,10230580,79708161,13894912,76038145,68943905,13107360,845424063}

    81675681

    Returns: 4

  32. {99738153,384603625,267324929,888225076,536872220,10519752,438956745,536906896,10488388,806389765,996931469}

    547393500

    Returns: 1

  33. {148505097,9968138,279901165,21364808,420616778,242240217,237647409,553785931,286923275,510683631,262666,403177473}

    970857035

    Returns: 1

  34. {1728546,134217768,2443272,145306112,30524285,108088394,146604098,378376805,3424362,701741823,143022144,3549698,136124928,482492234,476880904}

    146766442

    Returns: 3

  35. {55834219,39338052,35246144,138530884,172756992,768842501,5247040,169660484,685826797,36737092}

    176017476

    Returns: 1

  36. {356816896,88134401,332422313,81017006,153022226,530665286,244120130,109906088,942432034,612434039,352595712,23072768}

    358940417

    Returns: 1

  37. {788296620,417303771,176231689,333819356,610016834,544990723,234120575,922284117,151878394,153616523,42587531,649437857,53072898,112218950,911426102,709761536,841559829,779556521,143152138}

    195679627

    Returns: 2

  38. {276846850,347218560,524174827,746238065,57897412,586709014,338846722,755319712,91358243,757001330}

    347242379

    Returns: 0

  39. {503, 505, 152, 435, 491, 512, 1023, 355, 510, 500, 502, 255, 63, 508, 509, 511, 60, 250, 254, 346}

    510

    Returns: 5

  40. {503, 505, 152, 435, 491, 512, 1023, 355, 510, 500, 502, 255, 63, 508, 509, 511, 60, 250, 254, 346 }

    510

    Returns: 5

  41. {1, 2, 4 }

    7

    Returns: 1

  42. {1000, 1, 2, 4 }

    7

    Returns: 1

  43. {7 }

    7

    Returns: 1

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

    7

    Returns: 2

  45. {5, 2, 4, 52, 62, 9, 8, 3, 1, 11, 6 }

    11

    Returns: 3

  46. {12, 14 }

    15

    Returns: 0

  47. {1, 2, 3, 4, 5, 6, 7, 8, 9, 25, 26, 27, 28 }

    28

    Returns: 1

  48. {501, 505, 152, 435, 491, 510, 15, 502, 63, 509, 511, 60, 250, 254, 1, 7, 62, 255 }

    510

    Returns: 2

  49. {5, 2, 1, 3, 6, 4 }

    8

    Returns: 0

  50. {12345678, 2345678, 987654, 66666666, 66666660, 66666669, 66660666, 60666666, 66666866, 62666666, 63666666, 66666966, 66666996, 66666688, 66666600, 66666000, 66666888, 66666999, 66666222, 66667777 }

    45345565

    Returns: 0

  51. {8 }

    14

    Returns: 0

  52. {1 }

    7

    Returns: 0

  53. {1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20 }

    21

    Returns: 3

  54. {9, 5, 1 }

    14

    Returns: 0

  55. {3, 7 }

    1

    Returns: 0

  56. {1, 2, 4, 7, 13 }

    7

    Returns: 2

  57. {1546, 5465461, 4565461, 456451, 1546456, 1456546, 1456, 1676, 154664, 15446, 1455676, 154645, 1, 145646, 7671, 1556746, 5465, 15464565, 1546546, 1000000 }

    1

    Returns: 1

  58. {1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20 }

    1000000000

    Returns: 0

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: