Join UsSite Message
Only Premium Users can view the Question
Entering edit mode
Problem 1
Click here to Practice
Submit Problem to OJ
You are given an Array A of size N and an integer N.
Find the minimum vale K such that the number of subarrays of A having XOR value of at most K is atleast X.
- 1 <= N <= 105
- 1 <= X <= N x (N+2) / 2
- 1 <= A[i] <= 106
Sample Input :
4 7 1 2 3 4
Sample Output :
4
Explanation :
Given number of subarrays to be atleast 7, i.e. X = 7.
So if we select the value for K to be 3, number of subarrays of A having XOR value atmost 3 is 6.
If we select the minimum value for K to be 4, number of subarrays of A having XOR value atmost 4 is 8.
So, the minimum value of K for which number of subarrays of A is atleast 7, each of which have XOR value of atmost K is 4.
Problem 2
Given an subarray A of size N, you need to find a triplet say Ai, Aj, Ak with maximum sum which respects following two conditions :-
- i < j < k
- Ai <= Aj <= Ak
This problem is almost same as Mock Interview - II !
Entering edit mode
Problem 1
For now I can think of a O(N*logN*log(max(A[i]))) solution which in the worst case would be around O(400*N), pretty tight.
The idea is to first build a prefix xor trie.
Now, for some prefix xor p[i] we can query the trie for the number of prefix xors p[j], j < i which follow p[i]^p[j] <= K. Let this value be X[i].
We want the sum of X[i] for i in [0,n-1] to be atleast X.
Now this above part can be calculated for a fixed K. But we don't have a fixed K.
It turns out we can binary search for K. Why? Because the summation of X[i] is non-decreasing as we increase K.
Time Complexity Analysis
Binary Search for K - log(106)
Querying the trie - N*log(N)
Overall - N*logN*log(106)
If someone can improve this please comment.
Problem 2
From a glance, I can say that just maintain a non-decreasing stack iterating over the values of the array from left to right, and at last if the stack has more than 2 elements then the answer is the sum of top 3 elements of the stack.
I am pretty much sure this works.
Time Complexity Analysis
O(N) - Why? Every element gets popped and pushed only once.
For now I can think of a O(N*logN*log(max(A[i]))) solution which in the worst case would be around O(400*N), pretty tight.
The idea is to first build a prefix xor trie.
Now, for some prefix xor p[i] we can query the trie for the number of prefix xors p[j], j < i which follow p[i]^p[j] <= K. Let this value be X[i].
We want the sum of X[i] for i in [0,n-1] to be atleast X.
Now this above part can be calculated for a fixed K. But we don't have a fixed K.
It turns out we can binary search for K. Why? Because the summation of X[i] is non-decreasing as we increase K.
Time Complexity Analysis
Binary Search for K - log(106)
Querying the trie - N*log(N)
Overall - N*logN*log(106)
If someone can improve this please comment.
Problem 2
From a glance, I can say that just maintain a non-decreasing stack iterating over the values of the array from left to right, and at last if the stack has more than 2 elements then the answer is the sum of top 3 elements of the stack.
I am pretty much sure this works.
Time Complexity Analysis
O(N) - Why? Every element gets popped and pushed only once.
Loading Similar Posts
