### PROBLEM LINK:

**Author:** Andrii

**Tester:** Praveen Dhinwa

**Editorialist:** Ajay K. Verma

### DIFFICULTY:

Easy

### PREREQUISITES:

Ad-hoc, Basic maths.

### PROBLEM:

For a given list, the score is defined as the sum of size of the list and an additional number which could be 0, 1, 2, or 4 depending of whether the list has fewer than 4 unique elements, exactly 4 unique elements, exactly 5 elements or exactly 6 unique elements. Given a collection of lists, find the list with highest score, or indicate if there is a tie.

### QUICK EXPLANATION:

Compute the score of each list, and return the one with the highest score, or indicate that there is a tie.

### EXPLANATION:

In order to solve this problem, one only needs to compute the score of a list efficiently. If we can do so, then the rest of the problem is easy. Compute the score of all lists, and if there is a single list with the highest score, returns its id. On the other hand, if there are multiple lists with the highest score, then indicate that there is a tie.

The score of a list is the sum of its size and an additional number, which depends on the number of unique elements in the list. Since size of a list is easily computable, we only need to compute the number of unique elements in the list.

One could use a set to compute the number of unique elements in the list. However, since all the number are in the range [1, 6], we can use an integer to represent the set of elements in the list.

int CountUnique(vector v) { int signature = 0; for (int x : v) { signature |= (1 << x); } return __builtin_popcount(signature); }

For the list we use an integer signature such that the i-th bit of signature is set iff the integer i is in the input list. In order to count the number of unique elements in the list, one only needs to count the number of bits in signature which are set to 1. This can be done using the __builtin_pop_count() function. One could also precompute these values, and use them because the in this problem the signature will always lie in the range [1, 127].

### TIME COMPLEXITY:

O (N), where N is the sum of lengths of all lists.