Codechef programming set #22

MXZERO




#34:Make XOR zero
Olya has written N binary integers (i.e. either zero or one) on a blackboard. She recently learned about XOR operation. Now she wants to erase exactly one integer in the array so that the XOR of the remaining N - 1 numbers is zero. Please help her to calculate the number of ways of doing so.

Input

The first line of the input contains an 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 denoting the number of numbers that Olya has written on a blackboard.
The second line contains N space-separated integers A1A2, ..., AN denoting the numbers she had written.

Output

For each test case, output a single line containing the number of ways to erase exactly one integer so that the XOR of the remaining integers is zero. The ways where you erase the same integer but on different places in the given sequence are considered different.

Constraints

  • 1 ≤ T ≤ 20
  • 2 ≤ N ≤ 105
  • 0 ≤ Ai ≤ 1

Example

Input:
2
5
1 0 0 0 0
5
1 1 1 1 1

Output:
1
5

Explanation

Example case 1. If you erase the first number on the blackboard, then the XOR of the rest of numbers will be equal to zero.
Example case 2. You can erase any of the given 5 numbers, it will make the XOR of the rest equal to zero.
Solution:

import java.util.Scanner;


public class MXZERO
{
public static void main(String args[])
{
Scanner in=new Scanner(System.in);
int op=in.nextInt();
for (int a=0;a<op;a++)
{   int counter=0;
int sc=in.nextInt();
int aob[]=new int[sc];
for (int ab=0;ab<sc;ab++)
{
aob[ab]=in.nextInt();
if(aob[ab]==1)
counter++;
}
if(counter%2!=0) System.out.println(counter);
else System.out.println(sc-counter);
}
}

}

#35: Farmer And His Plot

Santosh has a farm at Byteland. He has a very big family to look after. His life takes a sudden turn and he runs into a financial crisis. After giving all the money he has in his hand, he decides to sell some parts of his plots. The specialty of his plot is that it is rectangular in nature. Santosh comes to know that he will get more money if he sells square shaped plots. So keeping this in mind, he decides to divide his plot into minimum possible square plots so that he can get maximum profit out of this.
So your task is to find the minimum number of square plots that can be formed out of the rectangular plot.

Input

The input consists of T number of test cases. T lines follow. Each line consists of two integers N and M which denotes the length and breadth of the rectangle.

Output

Output is a single line which denotes the minimum number of square plots that can be formed

Constraints

1<=T<=20 
1<=M<=10000 
1<=N<=10000
Input:
2
10 15
4 6

Output:
6
6

Solution:
import java.util.Scanner;


public class plot
{public static int gcd(int a,int b){
if(b==0)
return a;
else
return gcd(b,a%b);
}

public static void main(String args[])
{
Scanner in=new Scanner(System.in);
int b=in.nextInt();
while(b-->0)
{
int M = in.nextInt();
int N = in.nextInt();
int g=gcd(M,N);
int ans=(M/g)*(N/g);
System.out.println(ans);
}

}
}

#36:Piece of cake

This is a very easy warm-up problem.
You are given a string. Your task is to determine whether number of occurrences of some character in the string is equal to the sum of the numbers of occurrences of other characters in the string. 

Input

The first line of the input contains an integer T denoting the number of test cases. Each of the next T lines contains one string S consisting of lowercase latin letters.

Output

For each test case, output a single line containing "YES" if the string satisfies the condition given above or "NO" otherwise.

Constraints

  • 1 ≤ T ≤ 1000
  • 1 ≤ length of S ≤ 50
  • Subtasks

    Subtask #1[28 points]: S contains no more than 2 different letters.
    Subtask #2[72 points]: No additional conditions

    Example

    Input:
    4
    acab
    zzqzqq
    abc
    kklkwwww
    Output:
    YES
    YES
    NO
    YES

    Solution:



    import java.util.Arrays;
    import java.util.Scanner;

    public class PieceOfCake
    {
    public static void main(String args[])
    {
    Scanner in=new Scanner(System.in);
    int T=in.nextInt();
    in.nextLine();
    for (int a=0;a<T;a++)
    {
    String b=in.next();
    double len=b.length()/2;
    double len2=b.length();
    int max=0;
    while(b.length()!=0)
    {
    int count = b.length() - b.replace(b.charAt(0)+"","").length();
    max=Math.max(count, max);
    b=b.replace(b.charAt(0)+"","");
    }
    if(max==len&&(len2%2)==0) System.out.println("YES");
    else System.out.println("NO");
    }
    }
    }


    1. Posted by lol ik.

    Comments

    Popular Posts