Create a composition frequency map and operate on it accordingly. code
I am not able to understand your code . So can you please provide the step wise process to solve this .
It will be very helpful if you can provide step wise guide to solve this .
Okay, so here’s some notation. Note that We’re doing the analysis for a prefix A[1 \dots i] and at every index, we’re maintaining the following parameters.
- F^i(x) \rightarrow is the number of indices j \le i such that A_j=x in the prefix A[0,i] in other words, it’s the frequency of x in a prefix of length i in A.
F_c^i(f) \rightarrow is the number of x's such that F^i(x)=f- Frequency of frequency of any x.
Make sure you understand these correctly with a few examples.
- Start iterating over the array and for every index first update F^i and F^i_c and say A_i=x
- Note that since we’re increasing the frequency of A_i by one hence F_c^i(F^i(x)) reduces by one and F_c^i(F^i(x)+1) increases by one. So the following updates have to be made.
Now if i has to be a valid answer then note that the size of F_c cannot be greater than 2 as we want all numbers to have the same frequency after exactly one deletion.
If the size of F_c is exactly 1 then F_c^i = [[f,f_1]] which means that there are f_1 numbers with a frequency f. So i would be a valid answer in the following cases.
\rightarrow Either f=1 as you can just delete any one of the f_1 numbers and it would reduce the frequency of that element to zero and the rest of the elements will have the same frequency of 1.
\rightarrow Or f_1=1 which means there’s only one element in the entire prefix with a frequency of f, hence you can just delete any occurrence of that number, and the rest of the numbers would have the same frequency i.e. only one number with a frequency of f-1.
If the size of F_c is exactly 2 then F_c^i=[[f,f_1],[f',f_2]]. Then note that at least one of f_1 or f_2 has to be 1 and along with that say if f_1=1 then f-1=f' should hold true as deleting one element of frequency f would increase the frequency of frequency of f-1.
If the above conditions hold true then i is a valid solution. So we just return the biggest i valid i.
Thanks a Lot It helped me a lot to understand this problem.
I am sorry for replaying late actually when I come across a good problem, I get little distracted from my goal.
Can you also tell me if I want to be a consistant 4 star than how I sould prepare so that I can get to 4 star level by next 5 months ???
From where I should practice to code so that I can become a consistant 4 star coder by the next 4 months ??
I request you to help me for this problem too.
Problem Link :- Sell The Candies