Statistics

Problem Statement for "MarriageProblemRevised"

Problem Statement

There are several unmarried men and women living in a society where marriage is defined as either one husband with one or more wives, or one wife with one or more husbands. You are given a String[] preferences. The j-th character of the i-th element of preferences is '1' (one) if the i-th man and the j-th woman are willing to be part of the same marriage, and '0' (zero) otherwise.

Your task is to group these people into the minimum possible number of marriages. Each person must be a member of exactly one marriage, and each marriage must contain only willing members. Return the number of marriages, or -1 if this is not possible.

Definition

Class:
MarriageProblemRevised
Method:
neededMarriages
Parameters:
String[]
Returns:
int
Method signature:
int neededMarriages(String[] preferences)
(be sure your method is public)

Constraints

  • preferences will contain between 1 and 12 elements, inclusive.
  • The length of each element of preferences will be betwen 1 and 12, inclusive.
  • All elements of preferences will be of the same length.
  • Each element of preferences will contain only '0' (zeroes) and '1' (ones).

Examples

  1. {"111"}

    Returns: 1

    Here, we have one man and three women, and everybody is willing to be in the same marriage. Therefore, we only need one marriage.

  2. {"100", "010", "001"}

    Returns: 3

  3. {"00", "00"}

    Returns: -1

    Nobody is willing to be in the same marriage as anybody else, so there cannot be any marriages in this case.

  4. {"0001", "0001", "0001", "1111"}

    Returns: 2

  5. {"11101011","00011110","11100100","01010000","01000010","10100011","01110110","10111111"}

    Returns: 3

  6. {"1","1","1","0","1","0","1","1"}

    Returns: -1

  7. {"11110","11111","01000","11111","11011","10001","11111","11010"}

    Returns: 3

  8. {"01111100","11011111","10110101","10111110","11011110"}

    Returns: 3

  9. {"100111","001101","000011","001110","111001","100001","010001"}

    Returns: 3

  10. {"111111101","011111111","101101111","111111111","111111011"}

    Returns: 2

  11. {"0"}

    Returns: -1

  12. {"0","1","1","1","1","1","1","1"}

    Returns: -1

  13. {"111","111","111"}

    Returns: 2

  14. {"1010100","0110110","1001110","1011111","0001010","1000000","0010000","1100010","1110100","0111001"}

    Returns: 5

  15. {"1100100","1100001","1111100","1111011","1111001","1011110","1100111"}

    Returns: 3

  16. {"01011000110","00110111010","00001000101","10001110110"}

    Returns: 4

  17. {"01001","00101","11100","11110","11100","10011"}

    Returns: 3

  18. {"011111101111","011111100111","101110011001","110111111111","101110110110"}

    Returns: 2

  19. {"0010110111","1110000111","0101001111","1011010101"}

    Returns: 3

  20. {"1011101","1011111","0111110","1010110","1011110","0111001","0111111","1011111","1000010"}

    Returns: 3

  21. {"00010000","00000000","00000010","00000000","10000001","00001000","00000000","00000000"}

    Returns: -1

  22. {"011000000010","000110000010","011001101000","000000000000","000000000000","001000010001","010010000000","100100010000","000000000110","000000010000","001010000000","001010100000"}

    Returns: -1

  23. {"001000000000","100100100001","000000000000","000000000000","000000000000","000000100000","000010000000","000000001000","001000010101","000011100001","000010000000","010000011000"}

    Returns: -1

  24. {"001000011000","000000000000","000000000000","000010000000","000000000000","000000000000","000000000000"}

    Returns: -1

  25. {"010100000000","000000000000","000000000000","000000000000","000000000000","010000000000","000000000000","000000000000","000000001000","000000000000","000000000000","000000000000"}

    Returns: -1

  26. {"0000000","0010000","0000000","0000000","0000000","0000000","1000000","0000000","0000000","0000011","0100000","0000000"}

    Returns: -1

  27. {"000100000000","000000000010","000000001000","000100001000","000000000000","000000000000","000000000000","000000000010","000000000000","000000100000","010000000000","000000000000"}

    Returns: -1

  28. {"011000000010","000110000010","011001101000","000000000000","000000000000","001000010001","010010000000","100100010000","000000000110","000000010000","001010000000","001010100000"}

    Returns: -1

  29. {"001000000000","100100100001","000000000000","000000000000","000000000000","000000100000","000010000000","000000001000","001000010101","000011100001","000010000000","010000011000"}

    Returns: -1

  30. {"001000011000","000000000000","000000000000","000010000000","000000000000","000000000000","000000000000","000000010000","000001000000","100000000000","000000000010","000000000100"}

    Returns: -1

  31. {"000000000100","000000001000","000000110100","000010000000","000000000000","000000000000","001000000000","000000000001","000000011000","000100001000","000000000000","000000000101"}

    Returns: -1

  32. {"010000000010","000000000100","000010001000","000000100000","000000000100","000000000000","000000000000","000000000000","000000000000","000000000100","000000010010","000100000000"}

    Returns: -1

  33. {"010001101100","000001100000","010001001100","001010000000","000110100110","010101001000","110000001000","000000101101","110000000000","001000101001","000110110100","100001111000"}

    Returns: 6

  34. {"000100000000","011000001000","000000000001","000010010100","100001001000","000000000000","000000000001","000000110010","000000010000","000000000010","000100000000","000000010000"}

    Returns: -1

  35. {"111111111111","111111111111","111111111111","111111111111","111111111111","111111111111","111111111111","111111111111","111111111111","111111111111","111111111111","111111111111"}

    Returns: 2

  36. {"110011011011","111110111011","010011110010","010111101111","111111001111","100011111111","101000111111","111011111111","100111101101","011011111101","111111011111","101101011101"}

    Returns: 3

  37. {"011111101110","010010101101","111101110011","101011011111","111111101010","101101111111","101011110110","111110101011","111111110010","111111111111","011010111110","001111100000"}

    Returns: 3

  38. {"101111111011","111101011011","111110011101","010111111111","001111111100","110111111011","001101010101","111100111111","111110111010","111011001111","111011111111","110111101110"}

    Returns: 3

  39. {"110000111100","111100111110","111111001000","111011010011","001010101111","110111110111","011011111010","010010111000","101110111011","101101111111","011111010110","111111101111"}

    Returns: 3

  40. {"1","1","1","0","1","0","1","1","0","0","0","1"}

    Returns: -1

  41. {"101111100011"}

    Returns: -1

  42. {"011111001101","111110110101"}

    Returns: -1

  43. {"00","11","11","01","11","01","01","11","00","00","00","10"}

    Returns: -1

  44. {"101","010","011","100","000","001","100","000","000","000","110","011"}

    Returns: -1

  45. {"110000000001","000101101101","001000100101"}

    Returns: -1

  46. {"00010000","00000000","00000010","00000000","10000001","00001000","00000000","00000000"}

    Returns: -1

  47. {"011000000010","000110000010","011001101000","000000000000","000000000000","001000010001","010010000000","100100010000","000000000110","000000010000","001010000000","001010100000"}

    Returns: -1

  48. {"001000000000","100100100001","000000000000","000000000000","000000000000","000000100000","000010000000","000000001000","001000010101","000011100001","000010000000","010000011000"}

    Returns: -1

  49. {"001000011000","000000000000","000000000000","000010000000","000000000000","000000000000","000000000000"}

    Returns: -1

  50. {"010100000000","000000000000","000000000000","000000000000","000000000000","010000000000","000000000000","000000000000","000000001000","000000000000","000000000000","000000000000"}

    Returns: -1

  51. {"0000000","0010000","0000000","0000000","0000000","0000000","1000000","0000000","0000000","0000011","0100000","0000000"}

    Returns: -1

  52. {"100000001100","110000000000","001000000100","000100000000","000010000000","000001000000","000000100000","000000010000","000000101000","010000000100","010000000010","001000100001"}

    Returns: 10

  53. {"100010010100","010000000000","001000010000","001100000000","110011000010","000001001101","000000100000","000001010000","000000001100","000000100101","010000011010","000100000001"}

    Returns: 7

  54. {"100000000000","010100000011","001001001000","100110000000","000010000000","000001000000","000000100100","000000010000","000000111000","010101000101","000000101010","010100000001"}

    Returns: 8

  55. {"101000000010","010000000000","001000100000","000100000100","010110000000","000001000000","000000100000","000010011001","010000001000","000000000100","000010001010","000000010101"}

    Returns: 8

  56. {"100000000000","010000010000","001100000000","000100000010","000010000000","000001000101","000000101000","000000010100","000000001000","001000000100","000100000010","000001010001"}

    Returns: 9

  57. {"100000000000","010000000000","001010101101","000100000000","000011001000","000001010100","000000100000","000000010001","000001001000","001000000100","000000001010","000000000101"}

    Returns: 9

  58. {"100000000000","010000000000","001000001000","000100000000","000010001000","000001000000","000001100100","000000010000","001010001000","000100000100","000001010010","000110000001"}

    Returns: 10

  59. {"100000000000","010000100001","001000100010","000100000000","000010000100","000011100100","000000100011","000000011000","011000001000","000001101111","001100000010","001000100001"}

    Returns: 7

  60. {"100000000110","010000000000","001000000100","001100000000","100010000000","001001000000","000000110001","000000010000","100000001000","001000001100","010000000010","010010000001"}

    Returns: 9

  61. {"100001100000","010000110001","101100110100","001100110101","001110001010","000001000101","001010100100","101100010100","001000101001","100100100100","010000000010","111010000101"}

    Returns: 5

  62. {"100000000000","010000000000","001000000000","000100000000","010010000000","000001000000","000000100000","000000010000","000000001000","000000000100","000000000010","000000000001"}

    Returns: 12

  63. {"100000000010","010010010010","001010100101","001110000001","100011100000","011001000010","010000100000","001000110100","010000001000","000010000100","000100101010","010001100001"}

    Returns: 6

  64. {"100000000000","011100001000","001000101000","000100000000","100010000100","000001000000","000000100000","000000011000","000000001101","000000000100","000000000010","000000000001"}

    Returns: 10

  65. {"1","0","0","0","0","0","0","0","0","0","0","0"}

    Returns: -1

  66. {"111111111111", "111111000000", "000000111111"}

    Returns: 3

  67. {"100000000000","010000000000","001000000000","000100000000","000010000000","000001000000","000000100000","000000010000","000000001000","000000000100","000000000010","000000000001"}

    Returns: 12

  68. {"100100000000","010000000100","001000010000","100100000000","000010010000","100001000000","000000100000","000100010000","001000001000","000100000100","001000000010","000010000001"}

    Returns: 8

  69. {"100100000000","010000000100","001000010000","100100000000","000010010000","101001001000","000000100000","000100010000","001000001000","000100000100","001000000010","000010010001"}

    Returns: 8

  70. {"100000000000","010000000001","001000000010","000100000010","000010000010","000001000010","000000100000","000000010000","000000001000","000000000100","000000000010","000000000001"}

    Returns: 12

  71. {"100000000111","010000000000","001000000000","000100000000","000010000000","000001000000","000000100000","000000010000","000000001000","000000000100","000000000010","000000000001"}

    Returns: 12

  72. {"100000000000","010000010000","001000000000","000100100000","010010010000","010001000000","001000100010","000000010000","000000001000","000000000100","000000000010","000100000001"}

    Returns: 10

  73. {"100000000000","010000000000","001010000000","100100000010","000010000000","001001000010","000010100000","000000010000","000000001000","000000000100","000001000010","000000100001"}

    Returns: 10

  74. {"000100000000","000000000010","000000001000","000100001000","000000000000","000000000000","000000000000","000000000010","000000000000","000000100000","010000000000"}

    Returns: -1

  75. {"01100000001","00001100000","10011001101","00000000000","00000000000","00000001000","01000101001","00000001001","00010000000","00000011000","00000100000","01010000000"}

    Returns: -1

  76. {"00100011101","11001001000","01001000011","00000000001","00000111000","00000100000","10100000001","10100000100","00001101001","00001010100","00111000010","00010100001"}

    Returns: 6

  77. {"011000011000","000010000000","100100000100","101110010010","001000000000","000011010111","010001000001","000001010000","100001100000","100000010000","000000100010"}

    Returns: 8

  78. {"11011001010","00000101000","01000111001","10111010000","00111011111","11001110110","10010011110","10000111101","11111110011","10110110011","01010101001","00001011011"}

    Returns: 4

  79. {"001010001000", "000101000010", "111111111000", "111110111111", "111111101010", "001110100111", "100101101101", "100101101101", "111011001100", "111101101111", "001011111010", "101100011110" }

    Returns: 3

  80. {"11", "00" }

    Returns: -1

  81. {"111111111111", "111111111111", "111111111111", "111111111111", "111111111111", "111111111111", "111111111111", "111111111111", "111111111111", "111111111111", "111111111111", "111111111111" }

    Returns: 2

  82. {"111", "111", "111" }

    Returns: 2

  83. {"100110100110", "101001101110", "101110101011", "101101101111", "111100110110", "001111011011", "100110110110", "101111011100", "111000101011", "101111101111", "110100110100", "111111111111" }

    Returns: 3

  84. {"010000011111", "010000000000", "010000001110", "010101100000", "000000110000", "001000100001", "100010100000", "100100000100", "101010101010", "001010000001", "010001010101", "001010101100" }

    Returns: 6

  85. {"11111111111", "11111111111", "11111111111", "11111111111", "11111111111", "11111111111", "11111111111", "11111111111", "11111111111", "11111111111", "11111111111", "11111111111" }

    Returns: 2

  86. {"101010101010", "010101010101", "101010101010", "010101010101", "101010101010", "010101010101", "111111111111", "111111111111", "111111111111", "111111111111", "000111101011", "011011110101" }

    Returns: 3

  87. {"111011111101", "111011110111", "000101101000", "110110111101", "011100001111", "111110101011", "100011110111", "011101111111", "111111001110", "000110011001", "011100011010", "111011111011" }

    Returns: 3

  88. {"101010101010", "010011001100", "001110000011", "000100110010", "110010011100", "110101011001", "100111100001", "001101010000", "000100001000", "111110000100", "111111111010", "100001001101" }

    Returns: 4

  89. {"111111111000", "100011111110", "111100011111", "101101001110", "110111001111", "111111111110", "011100011111", "011110101111", "011111010100", "111010111110", "100111110111", "010110111110" }

    Returns: 3

  90. {"111111111111", "111111111111", "111111111111", "111111111111", "111111111111", "111111111111", "111111111111", "111111111111", "111111111111", "111111111111", "111110111111", "111111111111" }

    Returns: 2

  91. {"10", "10", "11" }

    Returns: 2

  92. {"10" }

    Returns: -1

  93. {"111000", "000111" }

    Returns: 2

  94. {"11110", "11110", "11110", "11110" }

    Returns: -1

  95. {"001000001001", "010000000111", "000010100111", "000010010110", "000000000000", "000100010100", "000100001101", "100001000110", "000100011010", "100000000101", "010110001110", "100000101001" }

    Returns: -1

  96. {"011110011111", "101111111111", "101000111111", "110111001111", "000011111111", "111011111111", "111011111111", "111111111011", "111011101111", "111101010011", "111111110011", "111110101011" }

    Returns: 3

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: