ss_96's blog

Print maximum frequency number in an array(with slight modification)
By ss_96, history, 7 years ago, In English

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.

  • Vote: I like it
  • +16
  • Vote: I do not like it

Comments Comments (7)
| Write comment?
»
7 years ago, # |
  Vote: I like it +1 Vote: I do not like it

why a -1?Isn't the question according to the rules set by codeforces?

→ Reply
»
7 years ago, # |
← Rev. 3   Vote: I like it +3 Vote: I do not like it

Group them according to their residuum modulo M (because 2 numbers cannot end up equal unless they are congruent modulo M). Now, in order to solve a group of numbers x1, x2, .., xL, all giving the same residuum modulo M, we'll consider, for simplicity, M = 1 and the array a[i] = x[i] / M. Now we can change each value by at most Q and want to have as many equal as possible. Let's sort the array a. Now, if in the changed array we have some numbers equal to some number P, then we can easily see what values could be changed to this number P: those in the interval [P — Q, P + Q]. So, the numbers that will be equal in the final array can be found on a contiguous subarray of a. Let's say the subarray is formed by the positions from i to j. In order for some value P to exist so that we could change the values of this array to a same P, we need to have a[j] — a[i] <= 2Q. If this condition holds, then we could change all the values to (a[i] + a[j]) / 2 for example. If the condition doesn't hold, obviously no P exists. Now you can use a pointer to move i and j in the same time. Hence, you get NlogN from the sorting + N from the second part time complexity. The memory is O(N)

→ Reply
  • »
    »
    7 years ago, # ^ |
    ← Rev. 5   Vote: I like it 0 Vote: I do not like it

    thanks for the answer, but how to group them with their modulo M,using hashtable? Also,it would be really helpful if you could share an editorial which describes a similar approach as I am not able to understand the first part of the algorithm completely.

    → Reply
    • »
      »
      »
      7 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      In order to group them you could sort them by (x[i] % M, x[i] / M) and then you have the groups as contiguous subarrays. Basically the first part was a claim that you could take some values to a same common one by modifying each with at most Q if and only if max — min <= 2Q. Then, applying it you can use the 2-pointer technique to advance with i and j in the same time (you advance with the j one step and then with the i as much as is needed in order to get a[j] — a[i] <= 2Q)

      → Reply
      • »
        »
        »
        »
        7 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        Alright,thanks a lot!

        → Reply
        • »
          »
          »
          »
          »
          7 years ago, # ^ |
          ← Rev. 3   Vote: I like it 0 Vote: I do not like it

          by sorting with (x[i] % M, x[i] / M),it means applying both 1 by one,right?

          → Reply
          • »
            »
            »
            »
            »
            »
            7 years ago, # ^ |
              Vote: I like it 0 Vote: I do not like it

            It means sorting them as pairs (you sort them after the first value and if this value is the same in both pairs that you should compare, then move on to the second value and decide based on which pair has the second value the biggest).

            → Reply