Hi everyone,recently i gave an OA in which i was not able to solve a question which was like this:
Given an array of N integers, find the maximum product of a subsequence and note the indexes which u consider for making the subsequence (i,j),their product should be perfect square.Also the array is 1 indexed.
Examples:
2(Test cases)
N=5
Array={2,4,3,1,5}
Output=5
N=8
Array={8,7,6,5,4,3,2,9}
Output=63
Constraints:
I don't remeber the constraints for T
1<=N<=2*10^5
1<=A[i]<=10^9
The sum of N over all test cases doesn't exceed 2x10^5.

for all single nums, i=j, we pick the largest one

for all indexes which are perfect squares, like 1,4,9,16, we take the product of all of them. since n<10**5, we will have at most 316 such indexes

for each prime<n/2, we need its odd powers as index: since n<10**5, it is at most 17 for 2, 11 for 3, 7 for 5......, for prime>=47, because 47 ^ 3>10 ** 5. we only have one odd power for them. e.g.
2: [2,8,32,128....]
3: [3,27...]
5: [5,125...]
7: [7,7^3...]
we take the combinations of the powers as long as possible to form sequences
sequences using 2's odd powers as the base: we will take [2, 8... 2^17], and 2's odd powers times other primes' odd powers (othe prime >2) and perfect squares (1,4,9,16...)
sequences with base=[2, 8, ..2^17] are:
base + perfect squares * base,
3's odd powers * (base + perfect squares*base),
5's odd powers * (base + perfect squares*base),
5's odd powers * 3's odd powers * (base + perfect squares*base)
sequences using 3's odd powers as the base: we will take [3, 27 ... ] and 3's odd powers times other primes' odd powers (othe prime >3) and perfect squares (1,4,9,16...)
sequences using 5's odd powers as the base: we will take [5, 125.. ] and 5's odd powers primes' odd powers(othe prime >5) and perfect squres (1,4,9,16...)
sequences using 7's odd powers as the base:.....
Sieve (Java)
My understanding of the problem:
For any subsequence that we picked, any pair of its index 1based (i, j)
must be a perfect square.
And we want to find the the subsequence such that the chosen indexes form the maximum product.
Observation
 Perfect square can always match with another perfect square index.
 Those that are not a perfect square can always be expressed as
X * Y
, where X
is a perfect square and Y
contains no perfect square factor. We must find other index that have Y
as its factor, and the indexes that match it is in the form of Y * Z
, where Z
is a perfect square. We will greedily take all from Z = 1, 4, 9, 16 , 25...,
. This guarantees the max product for a given Y
.
 In order to not waste time calculating the same sequence over and over again, notice that for any given number
X * Y
, only Y
matters, so we will run a sieve to find all the valid start first.
 Some examples of valid index sequence:
[3, 12], [5, 20], [3, 12, 27], ....
 I am not sure how to handle overflow in this problem. We can't mod because it will reduce 1000000008 to 1 and make it the smallest while it is the largest. I can use BigInteger in Java but for the sake of simplicity, I am using long only.
 The OP stated the
[3]
is also valid, so I am also including these single sequence into "odd" variable.
static boolean[] ok = new boolean[200002];
static boolean[] sq = new boolean[200002];
private static long solve(int[] A){
if (!ok[1]){ // let's compute this once for all testcases.
Arrays.fill(ok, true);
sq[1]=true;
for (int i = 2; i*i <= 200001; i++){
if (ok[i*i]){
sq[i*i] = true;
for (int j = i*i; j <= 200001; j += i*i){
ok[j] = false; // this can NOT be a valid start
}
}
}
}
long odd = 0; // max product with at least an index with an odd number of primes
long even = 1; // max product with all perfect squares
for (int i = 0; i < A.length; i++){
long cur = A[i];
if (ok[i+1]){ // this is a valid start
for (int j = 2; 1L*(i+1)*j*j <= A.length; j++){
cur *= A[(i+1)*j*j1];
}
}
odd = Math.max(odd, cur);
if (sq[i+1]){ // perfect square
even *= A[i];
}
}
return Math.max(odd, even);
}
Sample Testcases
System.out.println(solve(new int[]{2, 4, 3, 1, 5}));
System.out.println(solve(new int[]{8, 7, 6, 5, 4, 3 ,2, 9}));
System.out.println(solve(new int[]{2, 2, 3, 4, 5, 6, 7, 8, 9}));
System.out.println(solve(new int[]{1, 2, 3, 4, 5, 6}));
System.out.println(solve(new int[]{3, 3, 3}));
System.out.println(solve(new int[]{3, 3, 3, 3}));
System.out.println(solve(new int[]{5, 3, 30, 9, 3, 3, 3, 3, 15, 3, 3, 30}));
5
63
72
6
3
9
900