Statistics

Problem Statement for "GraphClique"

Problem Statement

You are given a String[] graphEdge representing an undirected graph.The j-th character of the i-th element of graphEdge is '1' (one) if there is an undirected edge between the i-th and j-th vertices, and '0' (zero) otherwise. Return a int[] containing the same number of elements as graphEdge, where the K-th (1-based) element is the number of different cliques of size K in the graph.

A clique is a non-empty set of vertices where every pair of vertices is directly connected by an edge in the graph. A clique of size K is a clique containing exactly K vertices.

Definition

Class:
GraphClique
Method:
allClique
Parameters:
String[]
Returns:
int[]
Method signature:
int[] allClique(String[] graphEdge)
(be sure your method is public)

Constraints

  • graphEdge will contain between 1 and 18 elements, inclusive.
  • Each element of graphEdge will contain exactly N characters, where N is the number of elements in graphEdge.
  • Each element of graphEdge will contain only the characters '0' (zero) and '1' (one).
  • The j-th character of the i-th element of graphEdge will be equal to the i-th character of the j-th element of graphEdge.
  • The i-th character of the i-th element of graphEdge will be '0' (zero).

Examples

  1. {"0"}

    Returns: {1 }

    A single vertex is also a clique of size 1.

  2. {"01","10"}

    Returns: {2, 1 }

  3. {"001","001","110"}

    Returns: {3, 2, 0 }

    Two cliques of size 2. One consists of vertices 0 and 2, and the other consists of vertices 1 and 2.

  4. {"0110","1001","1001","0110"}

    Returns: {4, 4, 0, 0 }

  5. {"00110","00010","10000","11000","00000"}

    Returns: {5, 3, 0, 0, 0 }

  6. {"010101","101010","010010","100010","011101","100010"}

    Returns: {6, 8, 1, 0, 0, 0 }

  7. {"0111111","1000100","1001101","1010010","1110000","1001001","1010010"}

    Returns: {7, 12, 6, 0, 0, 0, 0 }

  8. {"00010010","00011101","00010110","11101101","01010010","01110000","10101000","01010000"}

    Returns: {8, 13, 4, 0, 0, 0, 0, 0 }

  9. {"000101111","001000110","010100000","101000011","000000001","100000101","110001000","110100001","100111010"}

    Returns: {9, 15, 6, 1, 0, 0, 0, 0, 0 }

  10. {"0011111100","0011100011","1101111101","1110111111","1111000101","1011000010","1011000000","1011100010","0101010101","0111100010"}

    Returns: {10, 28, 30, 13, 2, 0, 0, 0, 0, 0 }

  11. {"00100100100","00001111010","10000110011","00001101111","01010011101","11110011000","01101101100","01011110001","10011010000","01110000001","00111001010"}

    Returns: {11, 28, 18, 3, 0, 0, 0, 0, 0, 0, 0 }

  12. {"001111101000","000010110000","100000011011","100000001001","110001101001","100010000101","110010000000","011000001001","101110010010","000001000010","001000001101","001111010010"}

    Returns: {12, 26, 11, 0, 0, 0, 0, 0, 0, 0, 0, 0 }

  13. {"0110100011101","1011000110001","1101000001110","0110100101101","1001001001010","0000001011100","0000110001000","0101000010001","1100010101000","1011111010000","1011010000000","0010100000000","1101000100000"}

    Returns: {13, 32, 19, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0 }

  14. {"01100101000110","10100010011001","11011001001000","00101111001010","00110010000100","10010010100101","01011101000010","10110010001100","00000100010110","01000000100110","01110001000100","10001101111001","10010010110001","01000100000110"}

    Returns: {14, 39, 19, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 }

  15. {"011011111010000","100111111101010","100000011001000","010011111010011","110100110010000","110100000110011","110110001110011","111110001011010","111100110000011","010001100010001","100111110101100","011000010010001","000000000010011","010101111000100","000101101101100"}

    Returns: {15, 53, 59, 22, 2, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 }

  16. {"0000011101111001","0000011111010001","0001110001010011","0010101100110010","0011011010110011","1110101101101111","1101110101011000","1101011011010011","0100100101010011","1110011110010111","1001110000011100","1111101111101101","1000011000110000","0000010001110001","0011110111000000","1110110111010100"}

    Returns: {16, 67, 103, 58, 13, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 }

  17. {"01001011100010000","10010110101010100","00000110111101110","01001000101111001","10010011111010001","01100000011100101","11101001101100001","10001010100111111","11111011001000001","00101100001100100","01111110110011011","00110111010000010","11011001001000101","00110001001000011","01100101010010001","00100001001101001","00011111101011110"}

    Returns: {17, 69, 86, 36, 5, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 }

  18. {"011001101101111110","100100110100001100","100000110011000011","010001001011111010","000000000111010000","100100011100110000","111000011011101111","011001101110000101","100101110010110010","110011010000100010","001110111001010111","101110100010100000","100101101101001111","100111001010000011","110100100000100111","110000110010101011","101100101110111101","001000110010111110"}

    Returns: {18, 79, 117, 70, 18, 2, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 }

  19. {"0"}

    Returns: {1 }

  20. {"01","10"}

    Returns: {2, 1 }

  21. {"000","000","000"}

    Returns: {3, 0, 0 }

  22. {"0001","0011","0100","1100"}

    Returns: {4, 3, 0, 0 }

  23. {"00011","00100","01011","10101","10110"}

    Returns: {5, 6, 2, 0, 0 }

  24. {"001001","000100","100110","011010","001100","100000"}

    Returns: {6, 6, 1, 0, 0, 0 }

  25. {"0001101","0001001","0000101","1100000","1010001","0000000","1110100"}

    Returns: {7, 8, 2, 0, 0, 0, 0 }

  26. {"01101011","10000001","10000101","00001101","10010010","00110000","10001000","11110000"}

    Returns: {8, 12, 3, 0, 0, 0, 0, 0 }

  27. {"001001000","001001101","110111001","001011010","001100110","111100010","010010000","000111000","011000000"}

    Returns: {9, 16, 7, 0, 0, 0, 0, 0, 0 }

  28. {"0111000010","1010100010","1100100010","1000001011","0110000101","0000000000","0001000000","0000100001","1111000000","0001100100"}

    Returns: {10, 15, 7, 1, 0, 0, 0, 0, 0, 0 }

  29. {"00000100011","00011011011","00001111001","01000000000","01100010001","10100010100","01101100111","01100000111","00000111001","11000011000","11101011100"}

    Returns: {11, 25, 15, 2, 0, 0, 0, 0, 0, 0, 0 }

  30. {"001011001111","001000110101","110111011001","001001101010","101000000110","101100010001","010100010000","011001100010","101100000111","110010001010","100110011100","111001001000"}

    Returns: {12, 32, 22, 4, 0, 0, 0, 0, 0, 0, 0, 0 }

  31. {"0100001110000","1010111000110","0100010010100","0000110101010","0101001101101","0111001000001","1100110100010","1001101010011","1010000101010","0001100010011","0110100000011","0101001111101","0000110101110"}

    Returns: {13, 37, 24, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 }

  32. {"00000011101111","00100111100111","01011010011000","00100010100100","00100011101011","01000011110110","11111100010110","11001100110000","11011101010001","00100111100001","10101000000010","11010110000001","11001110001000","11001000110100"}

    Returns: {14, 45, 34, 4, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 }

  33. {"010101111000100","100101011110000","000001000000101","110001110101001","000001111101100","111110000101011","100110001001111","110110000011001","110010100011000","010111000000011","010000011000010","000111111000110","101010100001000","000001100111000","001101110100000"}

    Returns: {15, 48, 38, 6, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 }

  34. {"0000010110001000","0001111001111001","0000010111010111","0100101011010011","0101000011000101","1110000000001000","0101000110001100","1010001000110010","1011101001010011","0111100010100001","0100000101010011","0111000110101101","1100011000010011","0010101000010011","0011000110101101","0111100011111110"}

    Returns: {16, 57, 56, 20, 2, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 }

  35. {"01111001111000110","10101111110100100","11000001101110111","10001010001000011","11010000000001001","01000010100010011","01010100111101001","11100000101111001","11100111001100101","11000010000000001","10110011100000011","01100011100000101","00100101000000001","00001011000000110","11100000100101001","10110100001001000","00111111111110100"}

    Returns: {17, 64, 74, 39, 8, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 }

  36. {"010000010010000000","100010010010100011","000100011100110011","001000011010010001","010000100010101001","000000101010101011","000011001001000011","111100000111000011","001101100000000110","001000010010000011","110111010101101001","000000110010010101","011011000010010110","001100000001101000","000011000010010100","000000001001101000","011001111100100001","011111110111000010"}

    Returns: {18, 61, 55, 16, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 }

  37. {"0"}

    Returns: {1 }

  38. {"01","10"}

    Returns: {2, 1 }

  39. {"001","000","100"}

    Returns: {3, 1, 0 }

  40. {"0001","0010","0101","1010"}

    Returns: {4, 3, 0, 0 }

  41. {"00010","00010","00001","11000","00100"}

    Returns: {5, 3, 0, 0, 0 }

  42. {"000100","001011","010110","101001","011001","010110"}

    Returns: {6, 8, 2, 0, 0, 0 }

  43. {"0100000","1000110","0000000","0000100","0101000","0100000","0000000"}

    Returns: {7, 4, 0, 0, 0, 0, 0 }

  44. {"01010001","10001001","00000010","10001000","01010010","00000010","00101100","11000000"}

    Returns: {8, 9, 1, 0, 0, 0, 0, 0 }

  45. {"000100001","001111001","010110010","111000001","011001010","010010111","000001001","001011001","110101110"}

    Returns: {9, 18, 10, 0, 0, 0, 0, 0, 0 }

  46. {"0010100000","0000000000","1001110111","0010101010","1011000111","0010000111","0001000010","0010110010","0011111101","0010110010"}

    Returns: {10, 20, 17, 5, 0, 0, 0, 0, 0, 0 }

  47. {"00111110011","00001000100","10001111111","10000110000","11100010011","10110000101","10111001101","00100010001","01100110011","10101000100","10101111100"}

    Returns: {11, 29, 27, 10, 1, 0, 0, 0, 0, 0, 0 }

  48. {"011101101011","100110011001","100110010011","111011111111","011101100101","100110100100","100111000101","011100001100","110100010110","000111111010","101100001100","111110100000"}

    Returns: {12, 39, 45, 18, 1, 0, 0, 0, 0, 0, 0, 0 }

  49. {"0100100111010","1001111000110","0001001000111","0110010010101","1100011101110","0101101000010","0110110011001","1000100011101","1001001101011","1000101110111","0111100101011","1110110011101","0011001111110"}

    Returns: {13, 45, 50, 17, 0, 0, 0, 0, 0, 0, 0, 0, 0 }

  50. {"00100111100110","00010111000011","10011101011010","01100000110101","00100100100001","11101011111011","11000101101111","11100110111110","10011111010001","00110101101011","00100111010110","10010011001000","11100111011001","01011110110010"}

    Returns: {14, 53, 74, 46, 12, 1, 0, 0, 0, 0, 0, 0, 0, 0 }

  51. {"001011010011011","001010100001110","110011011101111","000000000111101","111000100011111","101000000010000","010010001110101","101000000000001","001000100110011","001100101011010","100111101101010","111110000110001","011110100000010","111010001110100","101110111001000"}

    Returns: {15, 52, 57, 20, 2, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 }

  52. {"0100100000110110","1001010111011100","0000100101111100","0100111101101010","1011001101101011","0101001101100001","0001110100001111","0111111011101110","0100000101000101","0111110110110010","1011110101000001","1110000001000001","0111101100000001","1110001110000011","1001101101000101","0000111010111110"}

    Returns: {16, 64, 80, 38, 7, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 }

  53. {"01001101100000100","10001000001110100","00001000100010111","00000101111001011","11100000011011001","10010001011001101","00000000101110011","10010100111110010","10110011001111011","00011101001111011","01011111110010111","01000011110011001","01101011111101100","00011100110110001","11100100001010000","00110011111000000","00111110111101000"}

    Returns: {17, 70, 93, 42, 5, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 }

  54. {"011000101011100000","100111100110001110","100011100000001111","010011010011101010","011100011011001100","011100100001010001","111001001101010001","000110001110011010","100010110110100011","010000111000100011","110110011001110111","100111100010010111","100100001110010011","000001110011100101","011110010000000110","011010000011011011","011100011111101100","001001101111110100"}

    Returns: {18, 79, 103, 40, 2, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 }

  55. {"0"}

    Returns: {1 }

  56. {"01","10"}

    Returns: {2, 1 }

  57. {"010","101","010"}

    Returns: {3, 2, 0 }

  58. {"0"}

    Returns: {1 }

  59. {"01","10"}

    Returns: {2, 1 }

  60. {"011","101","110"}

    Returns: {3, 3, 1 }

  61. {"0111","1011","1101","1110"}

    Returns: {4, 6, 4, 1 }

  62. {"01111","10111","11011","11101","11110"}

    Returns: {5, 10, 10, 5, 1 }

  63. {"011111","101111","110111","111011","111101","111110"}

    Returns: {6, 15, 20, 15, 6, 1 }

  64. {"0111111","1011111","1101111","1110111","1111011","1111101","1111110"}

    Returns: {7, 21, 35, 35, 21, 7, 1 }

  65. {"01111111","10111111","11011111","11101111","11110111","11111011","11111101","11111110"}

    Returns: {8, 28, 56, 70, 56, 28, 8, 1 }

  66. {"011111111","101111111","110111111","111011111","111101111","111110111","111111011","111111101","111111110"}

    Returns: {9, 36, 84, 126, 126, 84, 36, 9, 1 }

  67. {"0111111111","1011111111","1101111111","1110111111","1111011111","1111101111","1111110111","1111111011","1111111101","1111111110"}

    Returns: {10, 45, 120, 210, 252, 210, 120, 45, 10, 1 }

  68. {"01111111111","10111111111","11011111111","11101111111","11110111111","11111011111","11111101111","11111110111","11111111011","11111111101","11111111110"}

    Returns: {11, 55, 165, 330, 462, 462, 330, 165, 55, 11, 1 }

  69. {"011111111111","101111111111","110111111111","111011111111","111101111111","111110111111","111111011111","111111101111","111111110111","111111111011","111111111101","111111111110"}

    Returns: {12, 66, 220, 495, 792, 924, 792, 495, 220, 66, 12, 1 }

  70. {"0111111111111","1011111111111","1101111111111","1110111111111","1111011111111","1111101111111","1111110111111","1111111011111","1111111101111","1111111110111","1111111111011","1111111111101","1111111111110"}

    Returns: {13, 78, 286, 715, 1287, 1716, 1716, 1287, 715, 286, 78, 13, 1 }

  71. {"01111111111111","10111111111111","11011111111111","11101111111111","11110111111111","11111011111111","11111101111111","11111110111111","11111111011111","11111111101111","11111111110111","11111111111011","11111111111101","11111111111110"}

    Returns: {14, 91, 364, 1001, 2002, 3003, 3432, 3003, 2002, 1001, 364, 91, 14, 1 }

  72. {"011111111111111","101111111111111","110111111111111","111011111111111","111101111111111","111110111111111","111111011111111","111111101111111","111111110111111","111111111011111","111111111101111","111111111110111","111111111111011","111111111111101","111111111111110"}

    Returns: {15, 105, 455, 1365, 3003, 5005, 6435, 6435, 5005, 3003, 1365, 455, 105, 15, 1 }

  73. {"0111111111111111","1011111111111111","1101111111111111","1110111111111111","1111011111111111","1111101111111111","1111110111111111","1111111011111111","1111111101111111","1111111110111111","1111111111011111","1111111111101111","1111111111110111","1111111111111011","1111111111111101","1111111111111110"}

    Returns: {16, 120, 560, 1820, 4368, 8008, 11440, 12870, 11440, 8008, 4368, 1820, 560, 120, 16, 1 }

  74. {"01111111111111111","10111111111111111","11011111111111111","11101111111111111","11110111111111111","11111011111111111","11111101111111111","11111110111111111","11111111011111111","11111111101111111","11111111110111111","11111111111011111","11111111111101111","11111111111110111","11111111111111011","11111111111111101","11111111111111110"}

    Returns: {17, 136, 680, 2380, 6188, 12376, 19448, 24310, 24310, 19448, 12376, 6188, 2380, 680, 136, 17, 1 }

  75. {"011111111111111111","101111111111111111","110111111111111111","111011111111111111","111101111111111111","111110111111111111","111111011111111111","111111101111111111","111111110111111111","111111111011111111","111111111101111111","111111111110111111","111111111111011111","111111111111101111","111111111111110111","111111111111111011","111111111111111101","111111111111111110"}

    Returns: {18, 153, 816, 3060, 8568, 18564, 31824, 43758, 48620, 43758, 31824, 18564, 8568, 3060, 816, 153, 18, 1 }

  76. {"0"}

    Returns: {1 }

  77. {"000000000000000000", "000000000000000000", "000000000000000000", "000000000000000000", "000000000000000000", "000000000000000000", "000000000000000000", "000000000000000000", "000000000000000000", "000000000000000000", "000000000000000000", "000000000000000000", "000000000000000000", "000000000000000000", "000000000000000000", "000000000000000000", "000000000000000000", "000000000000000000"}

    Returns: {18, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 }

  78. {"0110", "1001", "1001", "0110" }

    Returns: {4, 4, 0, 0 }

  79. {"001", "001", "110" }

    Returns: {3, 2, 0 }

  80. {"01111", "10111", "11011", "11101", "11110" }

    Returns: {5, 10, 10, 5, 1 }

  81. {"011111111111", "101111111111", "110111111111", "111011111111", "111101111111", "111110111111", "111111011111", "111111101111", "111111110111", "111111111011", "111111111101", "111111111110" }

    Returns: {12, 66, 220, 495, 792, 924, 792, 495, 220, 66, 12, 1 }

  82. {"011111111111111110", "101111111111111111", "110111111111111111", "111001111111111111", "111000111111111111", "111100011111111111", "111110001111111111", "111111001111111111", "111111110011111111", "111111110011111111", "111111111101111111", "111111111110111111", "111111111111011111", "111111111111101110", "111111111111110111", "111111111111111011", "111111111111111101", "011111111111101110" }

    Returns: {18, 146, 708, 2295, 5263, 8806, 10916, 10063, 6852, 3382, 1168, 265, 35, 2, 0, 0, 0, 0 }

  83. {"01111", "10100", "11000", "10000", "10000" }

    Returns: {5, 5, 1, 0, 0 }

  84. {"011111111111111111", "101111111111111111", "110111111111111111", "111011111111111111", "111101111111111111", "111110111111111111", "111111011111111111", "111111101111111111", "111111110111111111", "111111111011111111", "111111111101111111", "111111111110111111", "111111111111011111", "111111111111101111", "111111111111110111", "111111111111111011", "111111111111111101", "111111111111111110" }

    Returns: {18, 153, 816, 3060, 8568, 18564, 31824, 43758, 48620, 43758, 31824, 18564, 8568, 3060, 816, 153, 18, 1 }

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: