Message on Whatsapp 8879355057 for DSA(OA + Interview) + Fullstack Dev Training + 1-1 Personalized Mentoring to get 10+LPA Job
0 like 0 dislike
1,625 views
in Online Assessments by Expert (111,330 points)
edited by | 1,625 views

1 Answer

0 like 0 dislike
Best answer

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.

 

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

     

  2.  

    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

     

  3.  

    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
by Expert (111,330 points)