I have come across this tricky problem. An array of N elements should be converted to another array within k operations such that, distinct element's frequency should be

  • Equal and
  • A largest possible prime number

e.g. [2, 2, 2, 3, 3, 4] and k = 3 Here element 4 can be converted to 3 in one operation and by doing so, the frequency of all elements will be equal to (3) and that is the largest possible prime number we can get.

Another eg. [1, 1, 1, 1, 2, 2, 2, 6] and k = 3 we can convert two 1s into any new number x in 2 operations and convert one 2 to 6 in one operation. By doing so, the frequency of elements will be equal (2) and that is the largest possible prime number we get.

Also, we have to check whether it is possible within k operations.

Please help me out :) I couldn't understand the math behind these type of problems i.e. Min/Max no of operations required etc.,

Edited to add below steps tried so far:

1) Find the list of prime divisors of N which is less than N. for example, if N = 6 there are two prime numbers which can divide N i.e. 3 and 2 and if N = 8 there is only one prime number that can divide 8 that is 2.

2) Example no. 1, Take the other factor of largest found prime divisor, that will become the number of distinct elements in the array. i.e. N = 6 divided by prime 3 (the largest) is 2 and yes we need only 2 distinct numbers with frequency 3.

3) Take e.g. 1, the frequencies are [2]=3, [3]=2, [4]=1 comparing the first two frequencies. How to actually come up with required no.of operations to make the target array of two distinct elements of frequencies 3 ?

  • Whether by comparing each item from sorted(descending) frequency list with the largest prime divisor and add to HashSet and the number of operations is the sum of all HashSet values? In example no. 1, compare 3 with [2]=3 the difference is 0, compare 3 with [3]=2 the difference is 1. So, the num of operations will be 1 (0+1) ignoring the additional distinct elements frequencies.

Apply the same to example 2, and we need to add zero for new distinct element and ignore it.

After this I couldn't proceed because I thought I'm bit overthinking. Please try yours and help me.

Would really appreciate if a mathematical form/notation is defined for the above approach.

  • 1
    $\begingroup$ Please edit the question to add a reference to the original problem. $\endgroup$ – John L. Mar 2 '19 at 20:21
  • 2
    $\begingroup$ Have you thought about the simpler problems? For example, given k, how can you decide whether it is possible to change the array to an array where distinct element's frequency are the same? where the frequency is as large as possible? $\endgroup$ – John L. Mar 2 '19 at 20:27
  • $\begingroup$ I see a divisibility problem: please make me see the Computer Science angle. (A problem being presented as an assignment in some CS course doesn't make it a CS problem. Neither does being tasked to code a solution.) $\endgroup$ – greybeard Mar 3 '19 at 7:37
  • $\begingroup$ If you already know what the largest possible prime number is, can you solve the problem? $\endgroup$ – xskxzr Mar 3 '19 at 8:36
  • $\begingroup$ @xskxzr added some steps, please find whether it is useful and am I in the right direction to solve ? $\endgroup$ – Gokul E Mar 3 '19 at 11:17

Your Answer

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

Browse other questions tagged or ask your own question.