Given an array arr[] containing N integers and there are Q queries where each query consists of a range [L, R]. The task is to find whether all the elements from the given index range have even frequency or not.
Can Someone give better solution than O(n * q).
Solution given on this link is incorrect.
Example is below:
Input: arr[] = {100, 100, 200, 100}, Q[][] = {{1, 4}, {1, 2}}
Output:
No
Yes
Input: arr[] = {1, 1, 2, 2, 1}, Q[][] = {{1, 5}, {1, 4}, {3, 4}}
Output:
No
Yes
Yes
Solution 1:
You can replace each values (mapping) to big random values (32-bit as example) and use algorithm from your url. It will work with a sufficiently high probability.
Solution 2 (without xor):
Sort all queries by pair (L_i / sqrt(n), R_i). Now when moving between query (L_i, R_i) to (L_{i+1}, R_{i+1}) need to add/remove some elements. We do it element by element to support number of each value and count number different group size. Algorithm complexity is O(Q * log Q + (N + Q) * sqrt N).
Little explanation: After sort total number operation of add/delete elements equal to sum |L_i - L_{i + 1}| + |R_i - R_{i + 1}|.
Sum difference L: If L_i / sqrt(n) = L_{i + 1} / sqrt(n) then |L_i - L_{i + 1}| <= sqrt(n) (no more than Q * sqrt(n) for all query).
If L_i / sqrt(n) < L_{i + 1} / sqrt(n) then we go to some next block sqrt(n) and total number operation for it no more than O(n) (because L_i is increasing).
Sum difference R: If L_i / sqrt(n) = L_{i + 1} / sqrt(n) then R_i is increasing and total sum |R_i - R_{i + 1}| no more than O(n). Number different sqrt(n) blocks is n / sqrt(n) = sqrt(n). Then total operation no more O(n * sqrt(n)).
If L_i / sqrt(n) < L_{i + 1} / sqrt(n) then |R_i - R_{i + 1}| is O(n), but number of such cases is n / sqrt(n) = sqrt(n). Total is O(n * sqrt(n)).