All submissions for this problem are available.
Read problems statements in English, Mandarin Chinese and Russian as well.
Given an array A1,A2...AN, you have to print the size of the largest contiguous subarray such that
LCM of all integers in that subarray is equal to the product of all integers in that subarray.
For a subarray Ai,Ai+1...Aj where 1 ≤ i < j ≤ N to be valid: LCM(Ai,Ai+1...Aj) should be equal to Ai*Ai+1*...*Aj. You have to print the size of the largest valid subarray.
If no subarray satisfies output -1.
Note:A single element is not considered a subarray according to definition in this problem.
First line contains T, the number of testcases. Each testcase consists of N in one line followed by N integers in next line.
For each testcase, print the required answer in one line.
- 1 ≤ T ≤ 50
- 2 ≤ N ≤ 105
- 1 ≤ Ai ≤ 106
Input: 3 2 7 2 4 2 2 3 4 3 2 2 4 Output: 2 2 -1
Example case 1.LCM(2,7)=2*7. Therefore, subarray A1 to A2 satisfies.
Example case 2.The subarrays A2 to A3 and A3 to A4 are the maximum size possible.
Example case 3.No subarray will satisfy.
Warning: Use fast input/output. Large input files. Solutions may not pass in slower languages.
Update: Time limit for python=10s
|Tags||cook50 darkshadows dynamic-programming lcm math medium|
|Time Limit:||2.5 sec|
|Source Limit:||50000 Bytes|
|Languages:||ADA, ASM, BASH, BF, C, C99 strict, CAML, CLOJ, CLPS, CPP 4.3.2, CPP 4.9.2, CPP14, CS2, D, ERL, FORT, FS, GO, HASK, ICK, ICON, JAVA, JS, LISP clisp, LISP sbcl, LUA, NEM, NICE, NODEJS, PAS fpc, PAS gpc, PERL, PERL6, PHP, PIKE, PRLG, PYTH, PYTH 3.4, RUBY, SCALA, SCM guile, SCM qobi, ST, TCL, TEXT, WSPC|
Fetching successful submissions
If you are still having problems, see a sample solution here.