Contents
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
Subtasks
- 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() {
// your code goes here
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
{
// your code goes here
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
- Which Fuel is Cheaper CHEAPFUEL Solution
- Convex Hulk CONHULK Solution
- Functional Array FUNARR Solution
- Flip or Compress FLIPCOMP Solution
- Maximise the bridges MAXBRIDGE Solution
- Wildcard Replacement WLDRPL Solution
- Xor Equation XOREQN Solution
- Hill Sequence HILLSEQ Solution
- Weird Palindrome Making MAKEPAL Solution
- Equal Coins EQUALCOIN Solution Codechef
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))
We appreciate your solution submission we have added your solution on the post with credit, if possible please leave your codechef profile link to tag you.