1
$\begingroup$

There is an integer array and 2 variables Q and M.The output required is the number which has the maximum frequency in the array, but the catch is that each number in the array can be increased/decreased by M and that too Q number of times.

In case of multiple answers print the first one.

eg:

array:1,2,3,4 and Q=1,M=1

Answer:3 ,as the array can be transformed into 2,2,2,4 (here 2 appears 3 times in this array, adding 1 in 1 and subtracting 1 from 3.)

A hashtable can be used here,but can't understand how to handle the addition and subtraction of each number of the array.

Can anyone please suggest an approach for that part?

Thanks.

$\endgroup$
0
$\begingroup$

Start by sorting the array. Now go over the array using four pointers, left, center left, center right, and right. The two central pointers bracket all the occurrences of some value $x$. The left pointer points at the leftmost value which is at least $x-M$, and the right pointer points at the rightmost value which is at most $x+M$. Using the positions of these pointers you can calculate the maximum frequency of $x$.

Traversing the array should take linear time, so the entire algorithm takes time $O(n\log n)$.

For a possibly simpler solution, you can sort the array and then use a single pointer to traverse it. Treat this pointer as one of the central pointers from the previous algorithm, and find the locations of all other pointers in logarithmic time using binary search. Traversal now takes time $O(n\log n)$, but this doesn't increase the asymptotic running time of the algorithm.

$\endgroup$
  • $\begingroup$ thanks for the solution,didn't understand it completely though. $\endgroup$ – Saurabh Sep 25 '17 at 9:01
  • $\begingroup$ Can you please discuss about first 2 iterations of the algorithm if there are 10 numbers $\endgroup$ – Saurabh Sep 25 '17 at 9:02
  • $\begingroup$ Translating these ideas into an actual algorithm is your job. $\endgroup$ – Yuval Filmus Sep 25 '17 at 9:07
  • $\begingroup$ Alright,thanks for your time and effort. $\endgroup$ – Saurabh Sep 25 '17 at 9:08
  • $\begingroup$ will this algorithm take care of the Q parameter as well? $\endgroup$ – Saurabh Sep 25 '17 at 11:35

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.