Given an array and two ranges you need to find whether the subarray lying in these two ranges have mismatch of less than 1 or not when elements are compared correspondingly in a sorted order
For 10 Points
It’s quite easy you can just copy the two subarrays in the new array and sort it in O(N log N) and check the corresponding values for mismatch.if mismatch is more than 1 output NO else YES.
My Solution using this click here
For 30 Points
I used a simple approach in O(n) with some optimization.
What I did was made a frequency array for all values.Since A[i]<=100000 it’s feasible.
When u will create this frequency array we can easily maintain that values inserted in the vector are in sorted order only.
Now you can simply iterate over all values of given array from a to b and check the frequency of that value in two range [a b] and [c d] using Binary search.Two cases arise then:
IF diff in freq==1
we store the index of that value which is more in either range and increment our counter.
IF diff in freq>1
it means that 2 or more elements are different & hence no need for further search we can break the operation and print NO.
Now if till end diff in freq ==0
Answer is obvious YES
but if diff in freq ==1
You need to check that if there is some element which lies between these two different elements or correspondingly you can found the rank of those different element in both arrays.
If rank is same:
They will be at same position & hence output YES
They will lie at different position & hence output NO
I did was avoid checking same values by maintaining a bitset. It compensates for the time taken in the binary search to count frequency.
I changed a,b,c,d for overlapping ranges to avoid searching for the same element.
Here is the solution to my code implemented that way.