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 of elements of S the operation will return some element of S. The operation can be described by its "multiplication table": a square table where in row i and column j we have the result returned by the operation i*j. Ciel has already filled in row 0 of this table: for each j we know that 0 * j = firstRow[j].
Ciel's operation doesn't have to be symmetric: it is possible that for some i and j the operations i*j and j*i return two different values. However, Ciel does want her operation to be associative: for all a,b,c in S, (a*b)*c must be equal to a*(b*c). (Note that this includes cases when some or all of a,b,c are equal to each other.)
You are given the int[] firstRow with n elements. If there is a way to fill in the rest of the multiplication table so that the resulting operation is associative, find one such way and return a int[] with n*n elements: all elements of the entire multiplication table, listed in row major order. If there are multiple solutions you may return any of them. If there are no solutions, return {-1}. (I.e., if there are no solutions, return a int[] of length 1 containing the element -1.)
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 of elements of S the operation will return some element of S. The operation can be described by its "multiplication table": a square table where in row i and column j we have the result returned by the operation i*j. Ciel has already filled in row 0 of this table: for each j we know that 0 * j = firstRow[j].
Ciel's operation doesn't have to be symmetric: it is possible that for some i and j the operations i*j and j*i return two different values. However, Ciel does want her operation to be associative: for all a,b,c in S, (a*b)*c must be equal to a*(b*c). (Note that this includes cases when some or all of a,b,c are equal to each other.)
You are given the int[] firstRow with n elements. If there is a way to fill in the rest of the multiplication table so that the resulting operation is associative, find one such way and return a int[] with n*n elements: all elements of the entire multiplication table, listed in row major order. If there are multiple solutions you may return any of them. If there are no solutions, return {-1}. (I.e., if there are no solutions, return a int[] of length 1 containing the element -1.)
Definition
- Class:
- MultiplicationTable
- Method:
- getMultiplicationTable
- Parameters:
- int[]
- Returns:
- int[]
- Method signature:
- int[] getMultiplicationTable(int[] firstRow)
- (be sure your method is public)
Constraints
- firstRow will contain between 2 and 50 elements, inclusive.
- Each element in firstRow will be between 0 and |firstRow|-1, inclusive.
Examples
{1,2,0}Returns: {1, 2, 0, 2, 0, 1, 0, 1, 2 }The example return value corresponds to the following multiplication table: * | 0 1 2 --+----------- 0 | 1 2 0 1 | 2 0 1 2 | 0 1 2 In other words, this operation * can be defined using the following formula: i*j = (i+j+1) mod 3. We can easily verify that for any a,b,c both (a*b)*c and a*(b*c) evaluates to the same value: namely, to the value (a+b+c+2) mod 3.{1,1,1}Returns: {1, 1, 1, 1, 1, 1, 1, 1, 1 }This time we can use: i*j = 1.{0,0,1}Returns: {-1 }Row 0 already tells us that 0*0 = 0, 0*1 = 0, and 0*2 = 1. Let's take a=0, b=0, and c=2. On one hand we already know that (a*b)*c = (0*0)*2 = 0*2 = 1. On the other hand we also know that a*(b*c) = 0*(0*2) = 0*1 = 0. Hence, regardless of how we fill in the rest of the table, the resulting operation will never be associative.{0,1}Returns: {0, 1, 1, 1 }{2,3,0,1}Returns: {2, 3, 0, 1, 3, 0, 1, 2, 0, 1, 2, 3, 1, 2, 3, 0 }{3,4,5,0,2,1}Returns: {-1 }{0,1,2}Returns: {0, 1, 2, 0, 1, 2, 0, 1, 2 }
Back to all problems