List of Lists LISTLIST Solution
You are given a positive integer N and an array A of size N. There are N lists L1,L2…LN. Initially, Li=[Ai].
You can perform the following operation any number of times as long as there are at least 2 lists:
- Select 2 (non-empty) lists Li and Lj (i≠j)
- Append Lj to Li and remove the list Lj. Note that this means Lj 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 if it is not possible to achieve this via any sequence of operations.
Input Format
- The first line of input contains a single integer T, denoting the number of test cases. The description of T test cases follows.
- The first line of each test case contains an integer N.
- The second line of each test case contains N space-separated integers A1,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 if it is impossible to achieve such an array of lists.
Constraints
- 1≤T≤105
- 1≤N≤2⋅105
- 1≤Ai≤N
- Sum of N over all test cases doesn’t exceed 2⋅105
Subtasks
Subtask 1(100 points): Original constraints
Sample Input 1
3
1
1
2
1 2
3
1 1 2
Sample Output 1
0
-1
2
Explanation
Test case 1: There is only one list [1], and it trivially satisfies the condition so no operations are required.
Test case 2: There are only 2 ways to do an operation either take list [1] and append it to list [2] or take list [2] and append it to list [1]. In both cases, it is not possible to satisfy both given conditions at the same time. Hence, the answer is −1.
Test case 3: Here is one possible order of operations:
- Select the 3rd list [2] and append it to the 1st list [1].
- Then, select the 2nd list [1] and append it to the 1st list [1,2].
Finally, we are left with the single list [1,2,1] which satisfies the given conditions. It can be verified that it is impossible to do this using less than 2 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;
}
December Long Challenge 2021 Solution
- List of Lists LISTLIST Solution Codechef
- Valleys and Hills VANDH Solution Codechef
- Rock Paper Scissors ROPASCI Solution Codechef
- Squares Counting GRIDSQRS Solution Codechef
- Pyramid Traversal PYRAMIDMOVES Solution Codechef
- Increasing String INCREAST Solution Codechef
- Utkarsh and Placement tests UTKPLC Solution Codechef
- Check Mate CHECKMATE Solution Codechef