Problem Statement
Fox Ciel is creating a new binary operation.
The operation will be denoted $ and it will be defined on the finite set S = {0, 1, 2, ..., n-1}. I.e., for each ordered pair (i, j) of elements of S the operation (i $ j) will return some element of S.
For example, we can have S = {0, 1}, and we can define that (0 $ 0) = 0, (0 $ 1) = 1, (1 $ 0) = 0, and (1 $ 1) = 0.
Note that Ciel's operation is not necessarily symmetric. In other words, it is possible that for some i and j the operations (i $ j) and (j $ i) return two different values.
A nice concise description of the operation $ is its "multiplication table": a square table where in row i and column j we have the value (i $ j). You are given this "multiplication table" encoded as a int[] table with n^2 elements. For each valid i and j the operation (i $ j) returns the value table[i*n+j].
A subset T of S is called good if it has the following property: for any two elements i and j in T, (i $ j) is also in T.
Find and return the minimal size of a good subset of S. Note that the answer is always defined, as there always are some good subsets. For example, the entire set S is always good.
The operation will be denoted $ and it will be defined on the finite set S = {0, 1, 2, ..., n-1}. I.e., for each ordered pair (i, j) of elements of S the operation (i $ j) will return some element of S.
For example, we can have S = {0, 1}, and we can define that (0 $ 0) = 0, (0 $ 1) = 1, (1 $ 0) = 0, and (1 $ 1) = 0.
Note that Ciel's operation is not necessarily symmetric. In other words, it is possible that for some i and j the operations (i $ j) and (j $ i) return two different values.
A nice concise description of the operation $ is its "multiplication table": a square table where in row i and column j we have the value (i $ j). You are given this "multiplication table" encoded as a int[] table with n^2 elements. For each valid i and j the operation (i $ j) returns the value table[i*n+j].
A subset T of S is called good if it has the following property: for any two elements i and j in T, (i $ j) is also in T.
Find and return the minimal size of a good subset of S. Note that the answer is always defined, as there always are some good subsets. For example, the entire set S is always good.
Definition
- Class:
- MultiplicationTable2
- Method:
- minimalGoodSet
- Parameters:
- int[]
- Returns:
- int
- Method signature:
- int minimalGoodSet(int[] table)
- (be sure your method is public)
Constraints
- n will be between 1 and 50, inclusive.
- table will contain exactly n*n elements.
- Each element in table will be between 0 and n-1, inclusive.
Examples
{1,1,2,3, 1,0,3,2, 2,0,1,3, 1,2,3,0}Returns: 2
The smallest Good set is {0,1}, we can verify: 0 $ 0 = 1 0 $ 1 = 1 1 $ 0 = 1 1 $ 1 = 0{0,1,2,3, 1,2,3,0, 2,3,0,1, 3,0,1,2}Returns: 1
This time the answer is 1 since {0} is a Good set.{1,1,1,1, 2,2,2,2, 3,3,3,3, 0,0,0,0}Returns: 4
Now the only Good set is {0,1,2,3}.{0}Returns: 1
Back to all problems