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

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