List Of Lists LISTLIST Solution Codechef

Page Contents

List of Lists LISTLIST Solution

You are given a positive integer NN and an array AA of size NN. There are NN lists L1,L2…LNL1,L2…LN. Initially, Li=[Ai]Li=[Ai].

You can perform the following operation any number of times as long as there are at least 22 lists:

Select 22 (non-empty) lists LiLi and LjLj (i≠ji≠j)
Append LjLj to LiLi and remove the list LjLj. Note that this means LjLj cannot be chosen in any future operation.

Find the minimum number of operations required to obtain a set of lists that satisfies the following conditions:

The first element and last element of each list are equal.
The first element of all the lists is the same.

Print −1−1 if it is not possible to achieve this via any sequence of operations.

Input Format

The first line of input contains a single integer TT, denoting the number of test cases. The description of TT test cases follows.
The first line of each test case contains an integer NN.
The second line of each test case contains NN space-separated integers A1,A2,…,ANA1,A2,…,AN.

Output Format

For each test case, print a single line containing one integer: the minimum number of operations required to obtain an array of lists that satisfies the given conditions.

Print −1−1 if it is impossible to achieve such an array of lists.

Constraints

1≤T≤1051≤T≤105
1≤N≤2⋅1051≤N≤2⋅105
1≤Ai≤N1≤Ai≤N
Sum of NN over all test cases doesn’t exceed 2⋅1052⋅105

Subtasks

Subtask 1(100 points): Original constraints

Sample Input 1

Sample Output 1

0
-1
2

Explanation

Test case 11: There is only one list [1][1], and it trivially satisfies the condition so no operations are required.

Test case 22: There are only 22 ways to do an operation – either take list [1][1] and append it to list [2][2] or take list [2][2] and append it to list [1][1]. In both cases, it is not possible to satisfy both given conditions at the same time. Hence, the answer is −1−1.

Test case 33: Here is one possible order of operations:

Select the 33rd list [2][2] and append it to the 11st list [1][1].
Then, select the 22nd list [1][1] and append it to the 11st list [1,2][1,2].

Finally, we are left with the single list [1,2,1][1,2,1] which satisfies the given conditions. It can be verified that it is impossible to do this using less than 22 operations.

SOLUTION

Program Python: List of Lists LISTLIST Solution in Python

from collections import Counter
for _ in range(int(input())):
    n = int(input())
    l = list(map(int,input().split()))
    c = Counter(l)
    x = c.most_common(1)[0][1]
    #print(x)
    if n == 1 or x==len(l):
        print(0)
    elif n>=2 and x<=1:
        print(-1)
    else:
        print(len(l)-x+1)

Program C++: List of Lists LISTLIST Solution in C++

#include<bits/stdc++.h>
using namespace std;
 
int main()
{
    int t;
    cin>>t;
    while(t--)
    {
        int n;
        cin>>n;
        
        int a[n];
        for(int i = 0; i < n; i++)
        {
            cin>>a[i];
        }
        
        int mx = 1;
        int c = 1;
        sort(a,a+n);
        for(int i = 1; i < n; i++)
        {
            if(a[i] == a[i-1])
            {
                c++;
                mx = max(mx, c);
            }
            else{
                c=1;
            }
        }
        if(n==mx){
            cout<<0<<endl;
            continue;
        }
        if(mx==1){
            cout<<-1<<endl;
            continue;
        }
        cout<<(n-mx)+1<<endl;

    }
    return 0;
}