Even Tree

 You are given a tree (a simple connected graph with no cycles).You have to remove as many edges from the tree as possible to obtain a forest with the condition that : Each connected component of the forest contains even number of vertices
Your task is to calculate the number of removed edges in such a forest.

Input:
The first line of input contains two integers N and M. N is the number of vertices and M is the number of edges. 2 <= N <= 100.
Next M lines contains two integers u_i and v_i which specifies an edge of the tree. (1-based index)

Output:
Print a single integer which is the answer
Sample Input 

10 9

2 1

3 1

4 3

5 2

6 1

7 2

8 6

9 8

10 8

 

Sample Output :

2

 

import java.util.*;

 public class Solution{

    public static void main(String[] args){

        Scanner in = new Scanner(System.in);

        int N = in.nextInt();

        int M = in.nextInt();

        Integer[][] edges = new Integer[M][2];

        for(int i=0;i<M;i++){

            edges[i][0] = in.nextInt();

            edges[i][1] = in.nextInt();

            if(edges[i][0]>edges[i][1]){

                int tmp = edges[i][0];

                edges[i][0] = edges[i][1];

                edges[i][1] = tmp;

            }

        }

        Arrays.sort(edges,new Comparator<Integer[]>(){

            @Override

            public int compare(Integer[] int1, Integer[] int2){

                Integer v1 = int1[0];

                Integer v2 = int2[0];

                return v1.compareTo(v2);

            }

        });

        int[] count = new int[N];

        count[0] = N;

        for(int i=1;i<N;i++){

            ArrayList<Integer> a = new ArrayList<Integer>();

            a.add(i+1);

            int j = 0;

            while(j<a.size()){

                for(int m=j;m<M;m++){

                    if(edges[m][0]==a.get(j)){

                        if(!a.contains(edges[m][1])){

                            a.add(edges[m][1]);

                        }

                    }

                }

                j++;

            }

            count[i] = a.size();

        }

        int remove = 0;

        for(int c:count){

            if(c%2==0)

                remove++;

        }

        System.out.println(remove-1);                  

    }

}

Maximum Sub Array

Given an array of N elements, find the maximum possible sum of a 1. contiguous subarray 2. non-contiguous (not necessarily contiguous) subarray. Empty subarrays should not be considered.

Sample Run

input:
2
6
-1 -2 -3 -4 -5 -6
8
1 -16 15 23 -53 75 80 -24
output:
-1 -1
155 194

import java.io.*;
import java.util.*;
import java.text.*;
import java.math.*;
import java.util.regex.*;

public class Solution {
   
    //standard max function
    static int max(int x, int y) { return (y > x) ? y : x; }
   
    //modified version of Kadane's algorithm
    static int maxSubarrayContiguous(int[] arr, int indexMax) {
        //takes in first value just so it has _something_
        int maxSoFar = arr[0];
        int currMax = arr[0];
       
           for (int i = 1; i < indexMax; i++) {
                currMax = max(arr[i], currMax + arr[i]);
                maxSoFar = max(maxSoFar, currMax);
           }
           return maxSoFar;
        }
   
    static int maxSubarrayNonContiguous(int[] arr, int indexMax) {
        int sumMax = 0;
        int max = arr[0];
        boolean negArray = true;
        int res = 0;
        for (int i = 0; i < indexMax; i++) {
            //add all positive numbers
            if (arr[i] >= 0) {
                sumMax += arr[i];
                negArray = false;
            }
            //find the smallest negative number
            if (arr[i] >= max) { max = arr[i];}
        }
   
        if (negArray == false)
            res = sumMax;
        //if the array consists of all negative numbers
        //return the smallest number
        if (negArray)
            res = max;
       
        return res;
       
    }
   

    public static void main(String[] args) {
       
        Scanner in = new Scanner(System.in);
        //array to store continous solutions
        int[] testSolutionsC = new int[10];
        //array to store non-continuous
        int[] testSolutionsNC = new int[10];
        int resC;
        int resNC;
        int runs;
        runs = Integer.parseInt(in.nextLine());
       
        //go through the amount of solutions
        for (int i = 0; i < runs; i++) {
            String inputString;
            int[] arr = new int[100000];
            int indexMax = Integer.parseInt(in.nextLine());
           
            //tokenize input values;
            //all entries are separated by a space
            inputString = in.nextLine();
            int arrIndex=0;
            StringTokenizer st = new StringTokenizer(inputString);
            while(st.hasMoreTokens()) {
                arr[arrIndex] = Integer.parseInt(st.nextToken());
                arrIndex++;
            }
           
            //continuous solution
            resC = maxSubarrayContiguous(arr, indexMax);
            //non-continuous solution
            resNC = maxSubarrayNonContiguous(arr, indexMax);
           
            //add continuous solutions to array
            testSolutionsC[i] = resC;
            //add non-continuous solutions to array
            testSolutionsNC[i] = resNC;
           
        }
       
        //print out entries
        for(int i = 0; i < runs; i++) {
            System.out.print(testSolutionsC[i] + " ");
            System.out.print(testSolutionsNC[i]);
            System.out.println();
        }
       
    }
}

Fibonacci Modified

Problem Statement
A series is defined in the following manner:
Given the nth and (n+1)th terms, the (n+2)th can be computed by the following relation
Tn+2 = (Tn+1)2 + Tn

So, if the first two terms of the series are 0 and 1:
the third term = 12 + 0 = 1
fourth term = 12 + 1 = 2
fifth term = 22 + 1 = 5
… And so on.

Given three integers A, B and N, such that the first two terms of the series (1st and 2nd terms) are A and B respectively, compute the Nth term of the series.
Input Format
You are given three space separated integers A, B and N on one line.
Input Constraints
0 <= A,B <= 2
3 <= N <= 20

Output Format
One integer.
This integer is the Nth term of the given series when the first two terms are A and B respectively.
Note
    Some output may even exceed the range of 64 bit integer.
Sample Input
0 1 5 

Sample Output
5

Explanation
The first two terms of the series are 0 and 1. The fifth term is 5. How we arrive at the fifth term, is explained step by step in the introductory sections.
Solution
 
import java.io.*;
import java.util.*;
import java.text.*;
import java.math.*;
import java.util.regex.*;

public class Solution {

    public static void main(String[] args) {
        /* Enter your code here. Read input from STDIN. Print output to STDOUT. Your class should be named Solution. */
        int i,n;
        BigInteger a,b;
        Scanner sc=new Scanner(System.in);
        a =  sc.nextBigInteger();
        b =  sc.nextBigInteger();
        n = sc.nextInt();
        BigInteger [] val = new BigInteger[n];
        val[0] = a;
        val[1] = b;
        for(i=2;i<n;i++){
            val[i]= (val[i-1].pow(2)).add(val[i-2]);
        }
        System.out.println(val[i-1]);
   
    }
}

Kaprekar number

A Kaprekar number is a positive whole number n with d digits, such that when we split its square into two pieces - a right hand piece r with d digits and a left hand piece l that contains the remaining d or d−1 digits, the sum of the pieces is equal to the original number (i.e. l + r = n). The Task You are given the two positive integers p and q, where p is lower than q. Write a program to determine how many Kaprekar numbers are there in the range between p and q (both inclusive) and display them all.
Input Format
There will be two lines of input: p, lowest value q, highest value

Constraints:
0<p<q<100000

Output Format
Output each Kaprekar number in the given range, space-separated on a single line. If no Kaprekar numbers exist in the given range, print INVALID RANGE.
22223
99999
In the above range the follwoing numbers should have been generated :-
77778 82656 95121 99999

import java.io.*;
import java.util.*;

public class Solution {

    public static void main(String[] args) {
        /* Enter your code here. Read input from STDIN. Print output to STDOUT. Your class should be named Solution. */
        Scanner scan = new Scanner(System.in);
        int p = scan.nextInt();
        int q = scan.nextInt();
        boolean exist = false;
        if(q <= p){
            System.out.println("INVALID RANGE");
            return;
        }
        int m = 0,n = 0;
        long sqr = 0;
        String numb = "";
        String[] digits = new String[2];
        for(long i = p; i <= q; i++){
            if(i == 1)System.out.print(1 + " ");
            else{
            sqr = i*i;
            numb = String.valueOf(sqr);
            if(numb.length() % 2 == 0){
                digits[0] = numb.substring(0, numb.length()/2);
                digits[1] = numb.substring(numb.length()/2);
            }else{
                digits[0] = numb.substring(0, (numb.length() - 1)/2);
                digits[1] = numb.substring((numb.length() -1)/2);
            }
              if(digits[0] == "" )
                  m = 0;
              if(digits[1] == "")
                  n = 0;
              if(!digits[1].equals("") && !digits[0].equals("")){
              m = Integer.parseInt(digits[0]);
              n = Integer.parseInt(digits[1]);
              } 
            if(i == (m + n) ){
                System.out.print(i + " ");
                exist = true;
            }
        }
      }
        if(exist == false){
            System.out.println("INVALID RANGE");
        }
    }
}

Taum Bday White Gift and Black Gift Problem

import java.io.*;
import java.util.*;

public class TaumAndBday {

    public static void main(String[] args) {
        /* Enter your code here. Read input from STDIN. Print output to STDOUT. Your class should be named Solution. */
       
        Scanner sc = new Scanner(System.in);
        int numCases = sc.nextInt();
     
        for(int i = 0;i<numCases;i++){
            // have to use long because of the contraints which will not fit in int
            long numBlackGifts = sc.nextLong();
            long  numWhiteGifts = sc.nextLong();
            long  costBlackGift = sc.nextLong();
            long  costWhiteGift = sc.nextLong();
            long  conversionCost = sc.nextLong();
            long price = 0;
            if((costWhiteGift+conversionCost)<costBlackGift){
                price = (costWhiteGift+conversionCost)*numBlackGifts + (numWhiteGifts*costWhiteGift);
            }else if ((costBlackGift+conversionCost) < costWhiteGift){
                price = ((costBlackGift + conversionCost) * numWhiteGifts) + (numBlackGifts*costBlackGift);
            }else{
                price = (costBlackGift * numBlackGifts) + (costWhiteGift * numWhiteGifts);
            }
            System.out.println(price);
        }
    }
}

hours and minutes in words

Given a time in numbers we can convert it into words. For example :
5 : 00 ——  five o’clock
5 : 10 ——  ten minutes past five
5 : 15 ——  quarter past five
5 : 30 ——  half past five
5 : 40 ——  twenty minutes to six
5 : 45 ——  quarter to six
5 : 47 ——  thirteen minutes to six

Write a program which first inputs two integers, the first between 1 and 12 (both inclusive) and second between 0 and 59 (both inclusive) and then prints out the time they represent, in words.
Your program should follow the format of the examples above.

SAMPLE DATA :

1. INPUT :
TIME : 3,0
OUTPUT : 3 : 00 Three o’ clock
2. INPUT :
TIME : 7,29
OUTPUT : 7 : 29 Twenty nine minutes past seven
3. INPUT :
TIME : 6,34
OUTPUT : 6 : 34 Twenty six minutes to seven
4. INPUT :
TIME : 12,1
OUTPUT : 12 : 01 One minute past Twelve
5. INPUT :
TIME : 12,45
OUTPUT : 12 : 45 Quarter to One
6. INPUT :
TIME : 10,59
OUTPUT : 10 : 59 One minute to Eleven
7. INPUT :
TIME : 14,60
OUTPUT : Incorrect Input
Test your program for the data values given in the examples above and some random data.

 PROGRAM:-
 import java.io.*;
public class TimeInWords
{ 
    public static void main(String args[])throws IOException
    { 
        BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
       
        /* Inputting hours and minutes */
        System.out.print("Enter Hours : ");
        int h=Integer.parseInt(br.readLine());
        System.out.print("Enter Minutes : ");
        int m=Integer.parseInt(br.readLine());
       
        if((h>=1 && h<=12) && (m>=0 && m<=59)) // checking whether given input is legal or not.
        {
         /* creating an array containing numbers from 1-29 in words */

        String words[]={"", "One", "Two", "Three", "Four", "Five", "Six","Seven", "Eight", "Nine","Ten",
        "Eleven","Twelve","Thirteen","Fourteen","Fifteen","Sixteen","Seventeen","Eighteen","Nineteen",
        "Twenty","Twenty one", "Twenty two", "Twenty three", "Twenty four", "Twenty five",
        "Twenty six","Twenty seven","Twenty eight", "Twenty nine"};
        
         /* The below code is for finding whether to print the word 'minute' or 'minutes' */
         String plu, a;
         if(m == 1 || m == 59)
            plu = "Minute";
         else
            plu = "Minutes";
        
         /* When we have minutes from 31-59, we print the hour ahead of the given hour
          * like 6:55 will be 5 minutes to 7 and not 5 minutes to 6
          * when we print the hour ahead of the given hour, we face a problem at hour = 12
          * because if we print an hour ahead of 12, it will be thirteen, but we want 1
          * so the below code checks this & decides what hour to print in words when minutes is from 31-59
          */
         if(h==12)
            a = words[1]; //storing 'one' when hour is 12
         else
            a = words[h+1]; //if hour is not 12, then storing in words, an hour ahead of given hour
           
        /* The below code checks minutes and accordingly prints the time in words using array. */
         System.out.print("Output : "+h+":"+m+" ----- "); //printing the given time in numbers

         if(m==0)
            System.out.println(words[h]+" O' clock");
         else if(m==15)
            System.out.println("Quarter past "+words[h]);
         else if(m==30)
            System.out.println("Half past "+words[h]);
         else if(m==45)
            System.out.println("Quarter to "+a);
         else if(m<30) // condition for minutes between 1-29
            System.out.println(words[m]+" "+plu+" past "+words[h]);
         else // condition for minutes between 31-59
            System.out.println(words[60-m]+" "+plu+" to "+a);
        } //end of outer if

        else
            System.out.println("Invalid Input !"); //printing error message for illegal input
    }
}

Enter Hours : 7
Enter Minutes : 16
Output : 7:16 —– Sixteen Minutes past Seven

BigInteger factorial

Problem Statement
You are given an integer N. Print the factorial of this number.
N!=N×(N−1)×(N−2)×⋯×3×2×1

Note: Factorials of N>20 can't be stored even in a 64−bit long long variable. Big integers must be used for such calculations. Languages like Java, Python, Ruby etc. can handle big integers but we need to write additional code in C/C++ to handle such large values.
We recommend solving this challenge using BigIntegers.
Input Format
Input consists of a single integer N.

Output Format
Output the factorial of N.
Sample Input

25

Sample Output

15511210043330985984000000

 PROGRAM:-
import java.io.*;
import java.util.*;
import java.text.*;
import java.math.*;
import java.util.regex.*;

public class Solution
{
      public static void main(String[] args)
     {
           Scanner scn=new Scanner(System.in);
           int n=scn.nextInt();
           BigInteger factorial= BigInteger.ONE;  
           for (int i = 2; i <= n; i++)
           {
 
                 factorial = factorial.multiply(new BigInteger(String.valueOf(i)));

            }
            System.out.println(factorial);
    }
}

Find out the maximum number of topics a 2-person team can know. And also find out how many teams can know that maximum number of topics. pick 2 people out of N people

ACM ICPC Team:-
Problem Statement
You are given a list of N people who are attending ACM-ICPC World Finals. Each of them are either well versed in a topic or they are not. Find out the maximum number of topics a 2-person team can know. And also find out how many teams can know that maximum number of topics.
// pick 2 people out of N people

Input Format
The first line contains two integers N and M separated by a single space, where N represents the number of people, and M represents the number of topics. N lines follow.
Each line contains a binary string of length M. In this string, 1 indicates that the ith person knows a particular topic, and 0 indicates that the ith person does not know the topic.
//N people , M topic

Output Format
On the first line, print the maximum number of topics a 2-person team can know.
On the second line, print the number of 2-person teams that can know the maximum number of topics.
// condiser each topic's character array AS a binary or integer
// then screen all combination by taking "OR" operation and find a maximum number of "1" and the team
// to put the result , use a HashMap then put the team number and max count "Map<Integer,Integer>"
// key is to do "OR" operation in given array element.
//1. receive all necessary input parameters
//2. store to character array
//3. convert character array to integer array for "OR" operation
//4. screen all combination but there's no need to concern an order
//5. after 4, check number of "1" value and compare to previous max value if it exceeds or same
//6. iterate above
//7. print max and number of teams value - hashmap size

Constraints
2 ≤ N ≤ 500
1 ≤ M ≤ 500

Sample Input
4 5
10101
11100
11010
00101


Sample Output
5
2


Explanation
(1, 3) and (3, 4) know all the 5 topics. So the maximal topics a 2-person team knows is 5, and only 2 teams can achieve this.
Code


import java.util.HashMap;
import java.util.Map;
import java.util.Scanner;

public class ACMICPC {
    public static void main(String[] args) {
       
        Scanner in = new Scanner(System.in);
       
        //no of people
        int N = in.nextInt();
       
        //no of topic
        int M= in.nextInt();
       
        char[][] t = new char[N][M];
       

        //each pereons's topic data
        for(int i=0;i<N;i++){
            t[i]=in.next().toCharArray();
        }
       
        //convert to int type for "OR" operation
        int [][] p = new int[N][M];
       
        for(int i=0;i<N;i++){
            for(int j=0;j<M;j++){
            p[i][j]=(int)(t[i][j]-'0');
            }
        }
       
        //map for storing teams data
        Map<Integer,Integer> hmap = new HashMap<>();
       
        int count=0;
        int max=0;
       
       
        for(int i=0;i<N;i++){
         //first person
            int[] a=p[i];
            for(int j=i+1;j<N;j++){
             //second person
                int[] b=p[j];
                count=0;
                //"OR" operation and count total number of "1"
                for(int k=0;k<M;k++){
                    if((a[k]|b[k]) ==1)
                        count++;
                }
                //new MAX found , previous max and map data will be removed
                if(count>max){
                    max=count;
                    hmap.clear();
                    hmap.put(i,j);
                //same as max , count
                }else if(count==max){
                    hmap.put(i,j);
                }
            }           
        }
       
        //max number of "OR"
        System.out.println(max);
        //number of team who meet "max"
        System.out.println(hmap.size());
       
    }
}