# PROBLEM LINK:

**Setter:** debrc

**Tester:** mishra_roshan

**Editorialist:** debrc

# DIFFICULTY:

Easy-Medium

# PREREQUISITES:

Basic observations, Hashing/Mapping

# PROBLEM:

Given an sequence of N numbers A_1, A_2, .... A_N where N is always even

You have to convert the given sequence into a **weird sequence** where A_i=A_{i+2} and exactly has two distinct numbers.

Find out the minimum number of changes you need to make to make on that given sequence to make it a **weird sequence**.

# EXPLANATION

You have to make the odd indexed numbers into one distinct digit and even indexed numbers into one distinct digit but the number should not be same.

Firstly,

We will calculate the frequency of each odd indexed elements and frequency of each even indexed elements and store it in a map.

Then we will check if the maximum frequency element is different in both odd and even indexed elements.

If it is different we will just return-

(N/2-Frequency of the maximum frequency even indexed element

+

N/2-Frequency of the maximum frequency odd indexed element).

If it is not different we will return maximum of this both-

(N/2%-Frequency of the maximum frequency even indexed element

+

N/2-Frequency of the second maximum frequency odd indexed element)

AND

(N/2-Frequency of the second maximum frequency even indexed element

+

N/2-Frequency of the maximum frequency odd indexed element)

# TIME COMPLEXITY

Time complexity is O(NlogN) for sorting the frequency.

# SOLUTIONS:

## Setter's Solution

## Python

```
from collections import Counter
for _ in range(int(input())):
n=int(input())
a=list(map(int, input().split()))
# stores the odd indexed elements
odd=a[1::2]
# stores the even indexed elements
even=a[::2]
# Counts the frequency of each element in odd
odd_counter=Counter(odd)
# Counts the frequency of each element in even
even_counter=Counter(even)
odd=[]
even=[]
# making a nested list where
# each sub list = [frequency of i, element i]
for i in odd_counter:
odd.append([odd_counter[i],i])
for i in even_counter:
even.append([even_counter[i],i])
#sorting the nested list in descending order
odd=sorted(odd,reverse=True)
even=sorted(even,reverse=True)
if odd[0][1]!=even[0][1]:
print(n-odd[0][0]-even[0][0])
else:
min1=10**6
min2=10**6
min3=10**6
if len(odd)>1:
min1=n-odd[1][0]-even[0][0]
if len(even)>1:
min2=n-odd[0][0]-even[1][0]
if len(odd)==1 and len(even)==1:
min3=odd[0][0]
print(min(min1,min2,min3))
```

Feel free to Share your approach.

Suggestions are welcomed as always had been.