CODEWITHSUNDEEP
algorithmdata-structures
guptashekhar54
guptashekhar54

Reputation: 73

Queries to check whether all the elements in the given range occurs even number of times

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.

https://www.geeksforgeeks.org/queries-to-check-whether-all-the-elements-in-the-given-index-range-occur-even-number-of-times/

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

Upvotes: 2

Views: 1124

Answers (1)

aropan
aropan

Reputation: 636

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)).

Upvotes: 1

Related Questions