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 1-based (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*j-1];
}
}
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