Weird Palindrome Making MAKEPAL Solution

Weird Palindrome Making MAKEPAL Solution Codechef

by

Weird Palindrome Making MAKEPAL Solution

Naveej is from a tribe that speaks some weird language – their alphabet consists of NN distinct characters. He has an array A=[A1,A2,…,AN]A=[A1,A2,…,AN], where AiAi denotes the number of occurrences of the ii-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 ii (1≤i≤N)(1≤i≤N) and convert all occurrences of ii-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=2N=2 and A=[2,2]A=[2,2] and we consider the characters to be aa and bb, he can make both abbaabba and baabbaab, but abaaba is not allowed because it uses only 33 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 TT denoting the number of test cases. The description of TT test cases follows.
  • The first line of each test case contains a single integer NN – the size of the alphabet.
  • The second line contains NN space-separated integers: A1,A2,…,ANA1,A2,…,AN, where AiAi is the number of occurrences of the ii-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≤10001≤T≤1000
  • 1≤N≤2⋅1051≤N≤2⋅105
  • 1≤Ai≤1091≤Ai≤109
  • It is guaranteed that the sum of NN over all test cases does not exceed 2⋅1052⋅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=1N=1. Let the character be aa. We can make the following palindromic string: aaaaaaaa.
  • In the second test case, N=3N=3. Let the characters be aa, bb, cc. 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 bb to cc. Then, we can make the following palindromic string: acaccacaacaccaca.

Weird Palindrome Making MAKEPAL Solution is updated. Click Below

SOLUTION

Program Python: Weird Palindrome Making MAKEPAL Solution in Python

Code Credit: tashi (in comment section)

# 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

Codechef Long Challenges Solution

October Long Challenge 2021 Solution

September 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))

    Reply

Leave a Comment