A few days ago I came across a question which I was unable to solve.
Question:
Given an array of size N with N integers.
There are Q queries of the form L R K, where for each query in the subarray from index L to index R (inclusive) we have to print the last index of the longest prefix (of the subarray) such that all integers in the prefix are divisible by K.
My Approach:
Obviously, the O(q*n) solution was giving TLE. So I tried to solve the question by using segment trees (with Time Complexity: O(n+qlogn)) but the result was Memory Limit Exceeded for Big Test Cases.
Can anyone please share there approach for the problem statement?
Thank You.
What you want to ask either longest subarray full longest prefix of an array because both are different
Longest prefix of the subarray given in the query
Can you provide constraints, or a link to the actual problem?
Also, can you tell us what exactly you are storing in the segment tree that it gives memory limit exceeded.
Here is what I think you are asking : Each query is of the form L R K and you have to find the largest index i, L \leq i \leq R such that a[L], A[L+1], A[L+2] \cdots A[i] are all divisible by K.
An O(\log^2 n) per query solution :
Create a segment tree and in each node store the gcd of its segment ( This should not give Memory Limit Exceeded since we are storing just one integer per node and there are O(n) nodes ).
If a number divides all elements of a segment, it divides the gcd of those elements.
We can get the gcd of a segment in O(\log n) using this. Just binary search for the largest i.
An O(\log n) per query solution:
The range [L,R] would be divided into at most \log(n) segments by the segment tree. Find the leftmost segment whose gcd is not divisible by K ( You can have your query function return this node ). If there is no such node, then i is R.
Otherwise, i+1 ( such that i is as described above ) has to lie in this segment. Then, if the left child of this node has a gcd divisible by K, then i+1 must lie in the right child of this segment. Otherwise, i+1 must lie in the left child. Continue like this until the segment has length 1.
Personally, if the constraints allow, I would prefer the O(\log^2 n) per query solution since it is much easier to code.
1 Like
Sorry, I don’t have a link to the problem statement because it was a hiring challenge on HackerEarth and now the problems are removed.
I used the same approach of storing the gcd of each segment and then finding the longest contiguous segments whose GCD is divisible by K but it gave Memory Limit Exceeded.
I remember vaguely but the constraints were n<1e5 or 1e6
That memory limit is too harsh.
To optimize memory (which is really unnecessary), you can use int instead of long long int. If you use this implementation of a segment tree, you will need at most 2n-1 integers. Surely, they allow us to store the array, which takes n integers but don’t allow 2n-1?.
Personally, I have given 3 contests on HackerEarth and they were terrible. Wrong constraints, test data same as sample data, ambiguous problems etc. You can be pretty sure your solution was correct and it was not your fault that it did not pass.
1 Like