# Weird Palindrome Making MAKEPAL Solution Codechef

## Weird Palindrome Making MAKEPAL Solution

Naveej is from a tribe that speaks some weird language their alphabet consists of N distinct characters. He has an array A=[A1,A2,…,AN], where Ai denotes the number of occurrences of the i-th character with him.

He wants to make a palindromic string using all the characters he has (every character he has must be used in this string).

In order to make this possible, he can perform the following operation:

• Select an i (1≤i≤N) and convert all occurrences of i-th alphabet to any other alphabet of his choice.

Note that Naveej just wants to be able to make any palindrome, as long as every character is used. For example, if N=2 and A=[2,2] and we consider the characters to be a and b, he can make both abba and baab, but aba is not allowed because it uses only 3 characters.

Find the minimum number of operations required such that Naveej can make a palindromic string using all the characters he has. It can be proven that there always exists at least one sequence of operations allowing for the formation of a palindrome.

Input Format

• The first line of input contains a single integer T denoting the number of test cases. The description of T test cases follows.
• The first line of each test case contains a single integer N the size of the alphabet.
• The second line contains N space-separated integers: A1,A2,…,AN, where Ai is the number of occurrences of the i-th character with Naveej.

Output Format

For each test case, output a single line containing one integer the minimum number of operations required so that Naveej can make a palindromic string using all the characters he has.

Constraints

• 1≤T≤1000
• 1≤N≤2⋅105
• 1≤Ai≤109
• It is guaranteed that the sum of N over all test cases does not exceed 2⋅105

• Subtask 1 (100 points): Original constraints

Sample Input 1

``````2
1
4
3
4 3 1``````

Sample Output 1

``````0
1``````

Explanation

• In the first test case, N=1. Let the character be a. We can make the following palindromic string: aaaa.
• In the second test case, N=3. Let the characters be a, b, c. It is initially not possible to make a palindrome with the given occurrences of the characters. We perform 1 operation: Convert all the occurrences of b to c. Then, we can make the following palindromic string: acaccaca.

### SOLUTION

Program Python: Weird Palindrome Making MAKEPAL Solution in Python

``````# cook your dish here
T = int(input())
for i in range(0,T):
N = int(input())
A = [int(x) for x in input().split()]
if N==1:
print(0)
else:
v =[]
for i in A:
if i in range(1,1000000000,2):
v.append(i)
if len(v)==1:
print(0)
elif len(v)%2== 0:
print(int(len(v)/2))
else:
print(int((len(v)-1)/2))``````

Program C++: Weird Palindrome Making MAKEPAL Solution in C++

``````#include <iostream>
using namespace std;
int main() {
int t,n,i,x;
scanf("%d",&t);
while(t--)
{
int c=0;
scanf("%d",&n);
for(i=0;i<n;i++)
{
scanf("%d",&x);
if (x%2==1)
{
c++;
}
}
if (c%2==1)
{
c--;
}
printf("%d\n",c/2);
}
return 0;
}``````

Program Java: Weird Palindrome Making MAKEPAL Solution in Java

``````/* package codechef; // don't place package name! */
import java.util.*;
import java.lang.*;
import java.io.*;
/* Name of the class has to be "Main" only if the class is public. */
class Codechef
{
public static void main (String[] args) throws java.lang.Exception
{
Scanner sc= new Scanner(System.in);
int t=sc.nextInt();
int i;
while(t-- >0)
{
int c=0;
int n=sc.nextInt();
for(i=0;i<n;i++)
{
int x=sc.nextInt();
if (x%2==1)
{
c++;
}
}
if (c%2==1)
{
c--;
}
System.out.println(c/2);
}
}
}``````

## November Long Challenge 2021 Solution

### 2 thoughts on “Weird Palindrome Making MAKEPAL Solution Codechef”

1. T = int(input(“T”))
for i in range(0,T):
N = int(input(“N”))
A = [int(x) for x in input(“A”).split()]
if N==1:
print(0)
else:
v =[]
for i in A:
if i in range(1,1000000000,2):
v.append(i)
if len(v)==1:
print(0)
elif len(v)%2== 0:
print(int(len(v)/2))
else:
print(int((len(v)-1)/2))

• 