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.