PROBLEM STATEMENT
You are given a vector table representing a rectangular grid where each cell contains a
digit. The j-th character of the i-th element of table is the digit in the cell at row i, column
j of the grid.
Consider a sequence of distinct cells in this table where the row numbers of the cells (in the
order they appear in the sequence) form an arithmetic progression, and the column numbers also
form an arithmetic progression. Concatenate the digits in the cells of this sequence to obtain a
number.
Among all numbers that can be obtained in this manner, find and return the largest perfect square
(a square of an integer). If there are no perfect squares, return -1 instead.
DEFINITION
Class:FindingSquareInTable
Method:findMaximalSquare
Parameters:vector
Returns:int
Method signature:int findMaximalSquare(vector table)
NOTES
-An arithmetic progression is a sequence of numbers where the difference between each number and
the previous number is constant.
CONSTRAINTS
-table will contain between 1 and 9 elements, inclusive.
-Each element of table will contain between 1 and 9 characters, inclusive.
-All elements of table will be of the same length.
-Each element of table will contain only digits ('0'-'9').
EXAMPLES
0)
{"123",
"456"}
Returns: 64
Several three-digit numbers can be obtained: 123, 321, 456, and 654, but none of them is a perfect
square.
The largest obtainable perfect square is 64.
1)
{"00000",
"00000",
"00200",
"00000",
"00000"}
Returns: 0
0 is a perfect square. It is the largest one that can be obtained in this table.
2)
{"3791178",
"1283252",
"4103617",
"8233494",
"8725572",
"2937261"}
Returns: 320356
Take the i-th digit of each row i, and you'll get 320356 = 566 ~ 566.
3)
{"135791357",
"357913579",
"579135791",
"791357913",
"913579135"}
Returns: 9
It is known that a perfect square can't end with two odd digits. Therefore, the largest perfect
square that contains only odd digits is 9.
4)
{"553333733",
"775337775",
"777537775",
"777357333",
"755553557",
"355533335",
"373773573",
"337373777",
"775557777"}
Returns: -1
There exists no perfect square that contains only digits 3, 5, and 7.
5)
{"257240281",
"197510846",
"014345401",
"035562575",
"974935632",
"865865933",
"684684987",
"768934659",
"287493867"}
Returns: 95481
The sequence of digits that forms 95481 is shown in bold:
257240281
197510846
014345401
035562575
974935632
865865933
684684987
768934659
287493867
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)2010, TopCoder, Inc. All rights reserved.