Please provide hint for solving this problem ( see descriptions )

general
1

https://mycode.prepbytes.com/problems/arrays/LONGSTREAK

2

Create a composition frequency map and operate on it accordingly. code

1 Like
3

I am not able to understand your code . So can you please provide the step wise process to solve this .

4

It will be very helpful if you can provide step wise guide to solve this .

5

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.

Algorithm:

  • 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.
F^{i+1}(x)=F^i(x)+1 \rightarrow \text{Frequency increases by one}\\ F^{i+1}_c(F^i(x))=F_c^i(F^i(x))-1 \rightarrow \text{Subtract 1from previous frequency of frequency of x}\\ F^{i+1}_c(F^i(x)+1)=F^i_c(F^i(x)+1)+1 \rightarrow \text{Add 1 to new frequency of frequency of x}

  • 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.

1 Like
6

Thanks a Lot :slight_smile: It helped me a lot to understand this problem.

7

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 ???

8

From where I should practice to code so that I can become a consistant 4 star coder by the next 4 months ??

11

I request you to help me for this problem too.
Problem Link :- Sell The Candies