List of Lists Editorial || Geekstocode

Difficulty

Moderate

Prerequisites

  1. Arrays
  2. Lists

Problem

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:

  1. Select 2 (non-empty) lists Li and Lj(i≠j)
  2. 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:

  1. The first element and last element of each list are equal.
  2. 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

  1. The first line of input contains a single integer T, denoting the number of test cases. The description of T test cases follows.
  2. The first line of each test case contains an integer N.
  3. 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. 1≤T≤105
  2. 1≤N≤2⋅105
  3. 1≤Ai≤N
  4. Sum of N over all test cases doesn’t exceed 2.105

Input

3
1
1
2
1 2
3
1 1 2

Output

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 in C++

#include <bits/stdc++.h>
using namespace std;

int main() {
	int t; 
        cin>>t;
	while(t--)
	{
	    int n; 
            cin>>n;
	    vector<int> v(n);
	    set<int> s;
	    map<int,int> mp;
	    
	    for(int i = 0;i<n;i++)
	    {
	    cin>>v[i];   
	    s.insert(v[i]); 
	    mp[v[i]]++;      
	    }
	    
	    if(s.size() == 1)
	    cout<<"0";
	    else if(s.size() == n)
	    cout<<"-1";
	    else{
	        
	        int max = -1;
	        for(auto itr = mp.begin();itr!=mp.end();itr++)
	        {
	            if( itr->second > max)
	            max = itr->second;
	        }
	        cout<<n-max+1;
	        
	    }
	    cout<<endl;
	    
	    
	    
	}
	return 0;
}

In the above code, we have initially decremented the value of t and used a while loop. We then use a for loop to append the list. Then if s.size ==1 then it prints 0 else it prints -1.

Conclusion

In this post, we have discussed list of lists editorial and solved it using C++.

  1. ANgry Delta Editorial
  2. Mashmokh and ACM Editorial
  3. Little Girl and Maximum Sum Editorial

Leave a Comment

Your email address will not be published. Required fields are marked *