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
[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.
[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
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
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.
2 and if
N = 8 there is only one prime number that can divide
8 that is
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) Take e.g. 1, the frequencies are
=3, =2, =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
- Whether by comparing each item from sorted(descending) frequency list with the
largest prime divisorand add to
HashSetand the number of operations is the sum of all
HashSetvalues? In example no. 1, compare 3 with =
3the difference is
0, compare 3 with =
2the 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.