Statistics

Problem Statement for "FindingSquareInTable"

Problem Statement

You are given a String[] 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:
String[]
Returns:
int
Method signature:
int findMaximalSquare(String[] table)
(be sure your method is public)

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

  1. {"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.

  2. {"00000", "00000", "00200", "00000", "00000"}

    Returns: 0

    0 is a perfect square. It is the largest one that can be obtained in this table.

  3. {"123456789"}

    Returns: 81

    The largest perfect square in which its digits form an arithmetic progression is 81.

  4. {"3791178", "1283252", "4103617", "8233494", "8725572", "2937261"}

    Returns: 320356

    Take the i-th digit of each row i, and you'll get 320356 = 566 × 566.

  5. {"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.

  6. {"400000009"}

    Returns: 9000000

  7. {"3", "3", "1", "8", "7", "7", "3", "1", "6"}

    Returns: 31877316

  8. {"12121", "21212", "12121", "21212", "12121", "21212"}

    Returns: 121

  9. {"22344529","45667698","55554495","35419246","22363441","55790446","22287841","18252016"}

    Returns: 22363441

  10. {"1111111","1222221","1233321","1234321","1233321","1222221","1111111"}

    Returns: 1234321

  11. {"1999111","1922221","9233321","9234321","9233321","1922221","1111111"}

    Returns: 12321

  12. { "572402810", "975101461", "143754012", "305625757", "749356320", "658659337", "846847875", "689346593", "874938676"}

    Returns: 456976

  13. { "572402810", "975101461", "143754012", "305625757", "749356320", "658659337", "846848875", "689346593", "874938676"}

    Returns: 7884864

  14. {"553333733", "775337775", "777537775", "777357333", "755553557", "355533335", "373773573", "337373777", "775557777"}

    Returns: -1

    There exists no perfect square that contains only digits 3, 5, and 7.

  15. {"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

  16. {"155555555", "555555555", "555555555", "555555555", "555555555", "555555555", "555555555", "555555555", "555555558"}

    Returns: 81

  17. {"855555555", "555555555", "555555555", "555555555", "555555555", "555555555", "555555555", "555555555", "555555551"}

    Returns: 81

  18. {"655555558", "555555555", "555555555", "555555555", "555555555", "555555555", "555555555", "555555555", "155555554"}

    Returns: 81

  19. {"655555551", "555555555", "555555555", "555555555", "555555555", "555555555", "555555555", "555555555", "855555554"}

    Returns: 81

  20. {"844059007", "062846384", "503361052", "925295756", "774556341", "129146646", "221674051", "734719717", "699726092"}

    Returns: 5184

  21. {"844059007", "062846386", "503361092", "925295956", "774558341", "129186646", "221274051", "731719717", "629726092"}

    Returns: 21288996

  22. {"844059007", "062846386", "503361092", "925295956", "774558341", "129186646", "221274051", "731719717", "698661312"}

    Returns: 21316689

  23. {"844059007", "062846386", "503361091", "925295957", "774558349", "129186645", "221274056", "731719711", "698661312"}

    Returns: 21659716

  24. {"844059007", "062846386", "503361253", "925295957", "774558349", "129186645", "221274056", "731719711", "698663312"}

    Returns: 9409

  25. {"894059007", "062846386", "503661253", "925295957", "774550349", "129186645", "221274046", "731719711", "698663312"}

    Returns: 60516

  26. {"010496840", "383933626", "862842380", "847923348", "307068727", "467163882", "584002517", "975809449", "583816034"}

    Returns: 45369

  27. {"555563363", "556536633", "565555355", "353665656", "363553623", "633563333", "335346365", "535355533", "333565663"}

    Returns: 625

  28. {"555573373", "557537733", "575555355", "353775757", "373553793", "733573333", "335323375", "535355533", "373575773"}

    Returns: 729

  29. {"913511", "264296", "793669"}

    Returns: 961

  30. { "300000002", "000000000", "000000000", "000000000", "000000000", "000040000", "000000090", "000000000", "500000000"}

    Returns: 9000000

  31. {"0"}

    Returns: 0

  32. {"7"}

    Returns: -1

  33. {"9"}

    Returns: 9

  34. {"00000", "12000", "34500", "67890"}

    Returns: 6400

  35. {"177777777", "111120000", "777777771"}

    Returns: 121

  36. {"135", "357", "753", "327", "753", "357", "531"}

    Returns: 121

  37. {"593423"}

    Returns: 324

  38. {"380","119","444","646"}

    Returns: 441

  39. {"0","1"}

    Returns: 1

  40. {"7683","7707","7925","5741","4826"}

    Returns: 529

  41. {"47796"}

    Returns: 64

  42. {"8322953"}

    Returns: 25

  43. {"2","8","5","3","8","0","6","8"}

    Returns: 36

  44. {"3","4","9"}

    Returns: 49

  45. {"207866"}

    Returns: 0

  46. {"9","9","8"}

    Returns: 9

  47. {"512","506"}

    Returns: 25

  48. {"6797161"}

    Returns: 196

  49. {"897","776","417","609","000","290","634","069","927"}

    Returns: 9604

  50. {"756045","046718","327361","852649","316858","715396","240035","228843"}

    Returns: 85264

  51. {"453799069","998632401","853731699","517424073","800100202","611877566"}

    Returns: 804609

  52. {"964785927","528810021","518251269","884525119","451710900","926554375","138297666"}

    Returns: 1382976

  53. {"136563753","146162455","705266900","832717791","031674537","772726784","109758465"}

    Returns: 72726784

  54. {"453720859","835753862","170200788","146458404","611363268","405191114","910154614","727821015"}

    Returns: 404854641

  55. {"2738"}

    Returns: -1

  56. {"98708","93018","98104","85244","32959","33214","68497","91461"}

    Returns: 729

  57. {"808025440","544311395","054192331","304325682","889742445","863581357","244765195","772142846"}

    Returns: 6561

  58. {"58","39","24","17","69","32"}

    Returns: 625

  59. {"217","840","336","809","112","132","638","458","220"}

    Returns: 100

  60. {"92842148","40206861","58667881","07909076","59800902"}

    Returns: 961

  61. {"1941295","3316365","9454929","5442134"}

    Returns: 961

  62. {"3085","0220","1701","2647","4290"}

    Returns: 961

  63. {"5","5","6","1"}

    Returns: 16

  64. {"197986329","997942136","123963183","073193864","722494285","970621753","275147856","875177963","878677648"}

    Returns: 7569

  65. {"8894220","8380866","2749058","9864333","4039217","7226702","0973115"}

    Returns: 961

  66. {"980525037"}

    Returns: 729

  67. {"764436","786743","898982","877836"}

    Returns: 289

  68. {"9121007","5630078","2160523","0638906"}

    Returns: 12100

  69. {"6063554","6968194","6638264"}

    Returns: 324

  70. {"95354","35417","17945"}

    Returns: 441

  71. {"23997976","61061703","12129664","73026026","96270202","55619872","96202471","68001711"}

    Returns: 3600

  72. {"196765216","661013687","530799461","038128242","003297097"}

    Returns: 8649

  73. {"270","929","087","461"}

    Returns: 81

  74. {"488398316","338111160","553525233","649266174","356104171","624962479","097307609","725699881"}

    Returns: 59049

  75. {"093187582","703181640","925715694","080185884","098482986","162469721","908700789","699934565","970522038"}

    Returns: 6889

  76. {"03786","42398","15234","73845","49164","75132","19269","81174","93271"}

    Returns: 841

  77. {"489125639","807943645","202057210","004568507","317377899","900524003","611226506"}

    Returns: 5776

  78. {"972295178","485240801","421415863","608612596","409521588","153330423","047981405","802660339"}

    Returns: 8836

  79. {"427","846","992","651"}

    Returns: 81

  80. {"3147061","8119914","0109250","9176800","7842588","0088515","9787622"}

    Returns: 961

  81. {"44134325","15736221","23153321","51178553","59167310","37346665","41633757","67266016"}

    Returns: 784

  82. {"4595913","4974305","3995955","4339555","9375345","5544573","3589554"}

    Returns: 81

  83. {"5705200"}

    Returns: 25

  84. {"0455","5756"}

    Returns: 64

  85. {"761221217","116649219","214667727","776771107","167291771","316771174"}

    Returns: 11664

  86. {"25101558","84190526","50428920","99171251","08414460","01115248","48588194","96098619"}

    Returns: 1521

  87. {"3791178", "1283252", "4103617", "8233494", "8725572", "2937261" }

    Returns: 320356

  88. {"123", "456" }

    Returns: 64

  89. {"111", "191", "114" }

    Returns: 49

  90. {"000000000", "000000000", "000001000", "000000000", "000000000", "000000600", "000000000", "000000000", "000000090" }

    Returns: 900000000

  91. {"1" }

    Returns: 1

  92. {"999999999", "999999999", "999999999", "190909999", "999999999", "999999999", "999999999", "999999999", "999999999" }

    Returns: 900

  93. {"00000", "00000", "00200", "00000", "00000" }

    Returns: 0

  94. {"0000", "0300", "0060", "0000" }

    Returns: 36

  95. {"122222222", "222222222", "220222222", "222222222", "222202222", "222222222", "222222222", "222222222", "222222222" }

    Returns: 100

  96. {"9" }

    Returns: 9

  97. {"7643" }

    Returns: 64

  98. {"250" }

    Returns: 25

  99. {"6020501" }

    Returns: 625

  100. {"254" }

    Returns: 25

  101. {"812" }

    Returns: 81

  102. {"1111", "1611", "1141", "1111" }

    Returns: 64

  103. {"061" }

    Returns: 16

  104. {"641" }

    Returns: 64

  105. {"52" }

    Returns: 25

  106. {"553333733", "775337775", "777537775", "777357333", "755553557", "355533335", "373773573", "337373777", "775557777" }

    Returns: -1

  107. {"800", "010", "000" }

    Returns: 81

  108. {"3814" }

    Returns: 81

  109. {"257240281", "197510846", "014345401", "035562575", "974935632", "865865933", "684684987", "768934659", "287493867" }

    Returns: 95481

  110. {"999800010" }

    Returns: 99980001

  111. {"169081311" }

    Returns: 318096

  112. {"111", "161", "111" }

    Returns: 16

  113. {"3333", "3643", "3333" }

    Returns: 64

  114. {"2812" }

    Returns: 81

  115. {"0" }

    Returns: 0

  116. {"0000", "0200", "0050", "0000" }

    Returns: 25

  117. {"00000", "01210", "00000" }

    Returns: 121

  118. {"167" }

    Returns: 16

  119. {"604" }

    Returns: 64

  120. {"112421", "454212", "662461", "774691", "786899", "812689" }

    Returns: 8464

  121. {"640" }

    Returns: 64

  122. {"623", "140", "111" }

    Returns: 64

  123. {"164" }

    Returns: 64

  124. {"645" }

    Returns: 64

  125. {"0000", "0810", "0000" }

    Returns: 81

  126. {"777", "718" }

    Returns: 81

  127. {"000000000", "060400000", "000000000", "000000000", "000000000", "000000000", "000000000", "000000000", "000000000" }

    Returns: 4000000

  128. {"161" }

    Returns: 16

  129. {"777777", "717777", "772777", "777177", "777777" }

    Returns: 121

  130. {"00000", "00010", "00200", "01000", "00000" }

    Returns: 121

  131. {"26", "42" }

    Returns: 64

  132. {"819" }

    Returns: 81

  133. {"00001" }

    Returns: 10000

  134. {"257240281", "001110000", "014345401", "035562575", "974935632", "865865933", "684684987", "768934659", "287493867" }

    Returns: 94864

  135. {"60403" }

    Returns: 64

  136. {"1", "0", "0", "0", "0", "0", "0", "0", "0" }

    Returns: 100000000

  137. {"810" }

    Returns: 81

  138. {"677", "747", "777" }

    Returns: 64

  139. {"123456" }

    Returns: 64

  140. {"1111", "1411", "1191", "1111" }

    Returns: 49

  141. {"411", "191", "111" }

    Returns: 49

  142. {"128" }

    Returns: 81

  143. {"257240281", "000011100", "014345401", "035562575", "974935632", "865865933", "684684987", "768934659", "287493867" }

    Returns: 94864

  144. {"542352377" }

    Returns: 324

  145. {"35", "65" }

    Returns: 36

  146. {"4" }

    Returns: 4

  147. {"77777", "77877", "77717", "77777" }

    Returns: 81

  148. {"256" }

    Returns: 256

  149. {"333", "363", "334" }

    Returns: 64

  150. {"250", "000", "000" }

    Returns: 25

  151. {"2222", "2162", "2222", "2222" }

    Returns: 16

  152. {"7777777", "7000007", "7000007", "7001007", "7000007", "7000007", "7777777" }

    Returns: 100

  153. {"2819" }

    Returns: 81

  154. {"11111", "16111", "11411", "11111" }

    Returns: 64

  155. {"00000", "00000", "00250", "00000", "00000" }

    Returns: 25

  156. {"22222", "22122", "22222", "22122", "22222" }

    Returns: 121

  157. {"1641" }

    Returns: 64

  158. {"2000", "0410", "0190", "0000" }

    Returns: 49

  159. {"000625000" }

    Returns: 62500

  160. {"813" }

    Returns: 81

  161. {"9999", "9699", "9949", "9999" }

    Returns: 64

  162. {"999999999", "999999999", "999999999", "999999999", "999999999", "999999999", "999999999", "999999999", "999999999" }

    Returns: 9

  163. {"999950884" }

    Returns: 999950884

  164. {"633", "343", "333" }

    Returns: 64

  165. {"135791357", "357913579", "579135791", "791357913", "913579135" }

    Returns: 9

  166. {"457240281", "187510816", "018345211", "035069275", "974959632", "865169933", "684684987", "738934610", "287493800" }

    Returns: 23415921

  167. {"1000" }

    Returns: 100

  168. {"06", "40" }

    Returns: 64

  169. {"0000", "0640", "0000" }

    Returns: 64

  170. {"100220121" }

    Returns: 121022001

  171. {"162" }

    Returns: 16

  172. {"91449" }

    Returns: 441

  173. {"11110", "11101", "11011", "10111", "11111" }

    Returns: 10000

  174. {"6411" }

    Returns: 64

  175. {"000202021" }

    Returns: 10000

  176. {"1912" }

    Returns: 9

  177. {"7291" }

    Returns: 729

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: