 # FHL87 - EDITORIAL

Contest

Setter: debrc

Tester: mishra_roshan

Editorialist: debrc

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!=even:

print(n-odd-even)
else:
min1=10**6
min2=10**6
min3=10**6
if len(odd)>1:
min1=n-odd-even
if len(even)>1:
min2=n-odd-even
if len(odd)==1 and len(even)==1:
min3=odd
print(min(min1,min2,min3))
``````

Feel free to Share your approach.
Suggestions are welcomed as always had been.