[Solution] High Frequency solution codechef

High Frequency solution codechef – Chef has an array AA of length NN.

Let F(A)F(A) denote the maximum frequency of any element present in the array.

Table of Contents

[Solution] High Frequency solution codechef

  • If A=[1,2,3,2,2,1]A=[1,2,3,2,2,1], then F(A)=3F(A)=3 since element 22 has the highest frequency =3=3.
  • If A=[1,2,3,3,2,1]A=[1,2,3,3,2,1], then F(A)=2F(A)=2 since highest frequency of any element is 22.

Chef can perform the following operation at most once:

  • Choose any subsequence SS of the array such that every element of SS is the same, say xx. Then, choose an integer yy and replace every element in this subsequence with yy.

For example, let A=[1,2,2,1,2,2]A=[1,2,2,1,2,2]. A few examples of the operation that Chef can perform are:

  • [1,2,2,1,2,2][1,5,5,1,2,2][1,2,2,1,2,2]→[1,5,5,1,2,2]
  • [1,2,2,1,2,2][1,19,2,1,19,19][1,2,2,1,2,2]→[1,19,2,1,19,19]
  • [1,2,2,1,2,2][2,2,2,1,2,2][1,2,2,1,2,2]→[2,2,2,1,2,2]

Determine the minimum possible value of F(A)F(A) Chef can get by performing the given operation at most once.

Input Format

  • The first line of input will contain a single integer TT, denoting the number of test cases.
  • Each test case consists of two lines of input.
    • The first line of each test case contains a single integer NN denoting the length of array AA.
    • The second line contains NN space-separated integers denoting the array AA.

[Solution] High Frequency solution codechef

For each test case, output the minimum value of F(A)F(A) Chef can get if he performs the operation optimally.

Constraints

  • 1T50001≤T≤5000
  • 2N1052≤N≤105
  • 1AiN1≤Ai≤N
  • The sum of NN over all test cases won’t exceed 21052⋅105.

Sample Input 1 

3
4
1 2 1 2
5
1 1 1 1 1
6
1 2 2 1 2 2

Sample Output 1 

2
3
2

[Solution] High Frequency solution codechef Explanation

Test case 11: Chef cannot reduce the value of F(A)F(A) by performing any operation.

Test case 22: Chef can perform the operation [1,1,1,1,1][2,1,2,1,2][1,1,1,1,1]→[2,1,2,1,2]. The value of F(A)F(A) in this case is 33, which is the minimum possible.

Test case 33: Chef can perform the operation [1,2,2,1,2,2][1,5,5,1,2,2][1,2,2,1,2,2]→[1,5,5,1,2,2]. The value of F(A)F(A) in this case is 22, which is the minimum possible.

For Solution

Click Here

Leave a Comment