Maximum Dish Selection

Moderate

0/80

0 upvote

Problem statement

Ramu has N dishes of different types arranged in a row, represented by an array A, where A[i] denotes the type of the i-th dish. He wants to choose the maximum possible number of dishes, but he must adhere to two conditions:

1) He can only choose dishes of a single type.

2) No two chosen dishes can be adjacent to each other in the original row.

Your task is to determine which type of dish Ramu should choose to maximize his collection. If there's a tie (i.e., he can achieve the same maximum count with multiple dish types), he will choose the dish type with the smallest numerical value.

Detailed explanation ( Input/output format, Notes, Images )

Input Format:

The first line contains an integer T, the number of test cases.

For each test case:
  The first line contains a single integer N, the number of dishes.
  The second line contains N space-separated integers, A1, A2, ..., AN, representing the types of the dishes.

Output Format:

For each test case, print a single line containing one integer — the type of dish that Ramu should choose.

Note:

An element from array 'a' and an element from array 'b' can be part of only one pair. Once used, they cannot be used again to form another pair.

Sample Input 1:

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

Sample Output 1:

1
1
2

Explanation for Sample 1:

Test Case 1: A = [1, 2, 2, 1, 2]
  For type 1: Can pick A[0] and A[3]. Total = 2.
  For type 2: Can pick A[1] and A[4]. Total = 2.
  There is a tie between type 1 and type 2. The smallest type is chosen, so the answer is 1.
Test Case 2: A = [1, 1, 1, 1, 1, 1]
  For type 1: Can pick A[0], A[2], A[4]. Total = 3.
  The only type is 1, so the answer is 1.
Test Case 3: A = [1, 2, 2, 2, 3, 4, 2, 1]
  For type 1: Can pick A[0] and A[7]. Total = 2.
  For type 2: Can pick A[1], A[3], A[6]. Total = 3.
  For type 3: Can pick A[4]. Total = 1.
  For type 4: Can pick A[5]. Total = 1.
  The maximum number of dishes (3) can be picked if Ramu chooses type 2. The answer is 2.

Expected Time Complexity:

The expected time complexity is O(N^2).

Constraints:

1 ≤ T ≤ 1000
1 ≤ N ≤ 1000
1 ≤ A[i] ≤ 1000

Approaches (1)

Approach 1

Greedy

Time Complexity

Space Complexity

(100% EXP penalty)

Maximum Dish Selection

Console