/**
 * 
 * Problem Statement-
 * [Day of the Programmer](https://www.hackerrank.com/challenges/day-of-the-programmer/problem)  
 * 
 */
package org.javaaid.hackerrank.solutions.implementation.bruteforce;

import java.text.ParseException;
import java.text.SimpleDateFormat;
import java.util.Scanner;

/**
 * @author Kanahaiya Gupta
 *
 */
public class DayOfTheProgrammer {
	public static void main(String[] args) throws ParseException {
		Scanner sc = new Scanner(System.in);
		int y = sc.nextInt();
		SimpleDateFormat sdf = new SimpleDateFormat("dd.MM.yyyy");
		int d = 243;
		if (y >= 1700 && y <= 1917) {
			if (y % 4 == 0) {
				d = 244;
			}
		} else if (y >= 1919 && y <= 2700) {
			if (y % 400 == 0 || (y % 100 != 0 && y % 4 == 0)) {
				d = 244;
			}
		} else if (y == 1918) {
			d = 230;
		}
		int r = 256 - d;
		String date = r + "." + 9 + "." + y;
		System.out.println(sdf.format(sdf.parse(date)));
		sc.close();
	}
}

/**
 * 
 * Problem Statement-
 * [Minimum Absolute Difference in an Array](https://www.hackerrank.com/challenges/minimum-absolute-difference-in-an-array) 
 * 
 */
package com.javaaid.hackerrank.solutions.algorithms.sorting;

import java.util.Scanner;

/**
 * @author Kanahaiya Gupta
 *
 */
public class MinimumAbsoluteDifferenceInAnArray {
	public static void sort(int a[], int lo, int hi) {
		if (hi > lo) {
			int q = partition(a, lo, hi);
			sort(a, lo, q - 1);
			sort(a, q + 1, hi);
		}

	}

	public static int partition(int[] a, int lo, int hi) {
		int i = lo;
		int j = hi + 1;
		while (hi > lo) {
			while (a[++i] < a[lo])
				if (i == hi)
					break;
			while (a[--j] > a[lo])
				if (j == lo)
					break;

			if (i >= j)
				break;
			swap(a, i, j);
		}
		swap(a, lo, j);
		return j;

	}

	public static void swap(int a[], int i, int j) {
		int temp = a[i];
		a[i] = a[j];
		a[j] = temp;
	}

	public static void main(String[] args) {
		Scanner in = new Scanner(System.in);
		int n = in.nextInt();
		int[] a = new int[n];
		for (int a_i = 0; a_i < n; a_i++) {
			a[a_i] = in.nextInt();
		}
		sort(a, 0, a.length - 1);
		int min = Integer.MAX_VALUE;
		for (int i = 1; i < a.length; i++) {
			int diff = a[i] - a[i - 1];
			if (diff < min) {
				min = diff;
			}
		}
		System.out.println(min);
		in.close();
	}
}

/**
 * 
 */
package com.javaaid.hackerrank.solutions.languages.java.advanced;

import java.lang.annotation.ElementType;
import java.lang.annotation.Retention;
import java.lang.annotation.RetentionPolicy;
import java.lang.annotation.Target;
import java.lang.reflect.Method;
import java.util.Scanner;

/**
 * @author Kanahaiya Gupta
 *
 */

@Target(ElementType.METHOD)
@Retention(RetentionPolicy.RUNTIME)
@interface FamilyBudget {
	String userRole() default "GUEST";

	int moneySpend() default 100;
}

class FamilyMember {
	@FamilyBudget(userRole = "SENIOR")
	public void seniorMember(int budget, int moneySpend) {
		System.out.println("Senior Member");
		System.out.println("Spend: " + moneySpend);
		System.out.println("Budget Left: " + (budget - moneySpend));
	}

	@FamilyBudget(userRole = "JUNIOR", moneySpend = 50)
	public void juniorUser(int budget, int moneySpend) {
		System.out.println("Junior Member");
		System.out.println("Spend: " + moneySpend);
		System.out.println("Budget Left: " + (budget - moneySpend));
	}
}

public class JavaAnnotations {
	public static void main(String[] args) {
		Scanner in = new Scanner(System.in);
		int testCases = Integer.parseInt(in.nextLine());
		while (testCases > 0) {
			String role = in.next();
			int spend = in.nextInt();
			try {
				Class annotatedClass = FamilyMember.class;
				Method[] methods = annotatedClass.getMethods();
				for (Method method : methods) {
					if (method.isAnnotationPresent(FamilyBudget.class)) {
						FamilyBudget family = method.getAnnotation(FamilyBudget.class);
						String userRole = family.userRole();
						int budgetLimit = family.moneySpend();
						if (userRole.equals(role)) {
							if (budgetLimit >= spend) {
								method.invoke(FamilyMember.class.newInstance(), budgetLimit, spend);
							} else {
								System.out.println("Budget Limit Over");
							}
						}
					}
				}
			} catch (Exception e) {
				e.printStackTrace();
			}
			testCases--;
		}
		in.close();
	}
}

/**
 * 
 * Problem Statement-
 * [Recursion: Fibonacci Numbers](https://www.hackerrank.com/challenges/ctci-fibonacci-numbers/problem)
 * 
 */
package com.javaaid.hackerrank.solutions.tutorials.ctci;
/******************************************************************************
 *  Execution:    java  FibonacciNumber
 *  
 *  Algorithm:
 *  To solve this problem, we need to split the problem into a base case
 *   (the point at which we will stop performing operations) and a recursive case
 *   (the base case is not yet reached, so the function calls itself in such a way that we approach � and eventually reach � the base case).
 *   Base Case :
 *	  We must know the value of two consecutive elements to calculate the value of the next element in the sequence (i.e., ).
.*  fibonacci(n)=fibonacci(n-1)+fibonacci(n-2)   if n>1
 *	  fibonacci(n==0)=0
 *  fibonacci(n==1)=1
 *  Thus, we consider the base case to be when we reach the first two elements of the series.
 *  Recursive Case:
 *  We've already defined our base case, so we define our recursive case to be everything 
 *  else not satisfying the base case. 
 *  This means that any other valid value of  (i.e., whenever ) should be handled recursively.
 *   So how do we call the function in a way that guarantees we'll eventually reach the base case?
 ******************************************************************************/

import java.util.Scanner;

/**
 * The {@code FibonacciNumber} class represents a number generator to generate
 * Fibonacci Number
 * 
 * @author Kanahaiya Gupta
 */
public class FibonacciNumber {

	/**
	 * This method is used to generate the nth fibonacci number
	 * 
	 * @param n
	 * @return a nth fibonacci number
	 */
	public static int fibonacci(int n) {
		if (n == 0 || n == 1)
			return n;
		return fibonacci(n - 1) + fibonacci(n - 2);

	}

	/**
	 * Unit tests the {@code FibonacciNumber}
	 * 
	 * @param args
	 */
	public static void main(String[] args) {
		Scanner scanner = new Scanner(System.in);
		int n = scanner.nextInt();
		scanner.close();
		System.out.println(fibonacci(n));
	}
}

/**
 * 
 * Problem Statement-
 * [Big Sorting](https://www.hackerrank.com/challenges/big-sorting/problem)
 * 
 */
package com.javaaid.hackerrank.solutions.algorithms.sorting;

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

/**
 * @author Kanahaiya Gupta
 *
 */
public class BigSorting {
	public static void main(String[] args) {
		Scanner in = new Scanner(System.in);
		int n = in.nextInt();
		String[] unsorted = new String[n];
		for (int unsorted_i = 0; unsorted_i < n; unsorted_i++) {
			unsorted[unsorted_i] = in.next();
		}

		Arrays.sort(unsorted, new Comparator() {

			public int compare(String s1, String s2) {
				return compareStrings(s1, s2);
			}
		});
		printArray(unsorted);
		in.close();
	}

	private static int compareStrings(String s1, String s2) {
		if (s1.length() < s2.length()) {
			return -1;
		} else if (s1.length() > s2.length()) {
			return 1;
		}
		for (int k = 0; k < s1.length(); k++) {
			if ((int) s1.charAt(k) < (int) s2.charAt(k))
				return -1;
			if ((int) s1.charAt(k) > (int) s2.charAt(k))
				return 1;

		}
		return 0;

	}

	private static void printArray(String[] unsorted) {

		for (String string : unsorted) {
			System.out.println(string);
		}

	}

}

/**
 * 
 */
package com.javaaid.hackerrank.solutions.languages.java.advanced;

import java.security.MessageDigest;
import java.security.NoSuchAlgorithmException;
import java.util.Scanner;

/**
 * @author Kanahaiya Gupta
 *
 */
public class JavaMD5 {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		String s = sc.next();
		System.out.println(getMD5(s));
		sc.close();
	}

	private static String getMD5(String s) {
		StringBuffer sb = new StringBuffer();
		try {
			MessageDigest md = MessageDigest.getInstance("MD5");
			byte[] result = md.digest(s.getBytes());
			for (int i = 0; i < result.length; i++) {
				String hex = Integer.toHexString(0xff & result[i]);
				if (hex.length() == 1)
					sb.append('0');
				sb.append(hex);

			}
		} catch (NoSuchAlgorithmException e) {
			// TODO Auto-generated catch block
			e.printStackTrace();
		}

		return sb.toString();
	}

}

/**
 * 
 * Problem Statement-
 * [Recursive Digit Sum](https://www.hackerrank.com/challenges/recursive-digit-sum/problem) 
 * 
 */
package com.javaaid.hackerrank.solutions.algorithms.recursion;

import java.math.BigInteger;

public class RecursiveDigitSum {

	// method 1 -> recursive solution
	static int digitSum(String n, int k) {
		long superDigit = getSuperDigit(n);
		long n1 = getSuperDigit(superDigit);
		long k1 = getSuperDigit(k);

		long result = n1 * k1;

		while (result / 10 != 0) {
			result = getSuperDigit(result);
		}

		return (int) result;
	}

	private static long getSuperDigit(String n) {
		if (n == null || n.isEmpty())
			return 0;
		return (n.charAt(0) - '0') + getSuperDigit(n.substring(1));
	}

	private static long getSuperDigit(long n) {
		if (n / 10 != 0)
			return (n % 10) + getSuperDigit(n / 10);
		return (n % 10);
	}

	// method 2 > Iterative solutions hint -->http://applet-magic.com/digitsummod9.htm
	static int digitSumUsingMathTrick(String n, int k) {
		BigInteger n1 = new BigInteger(n);
		n1 = n1.multiply(new BigInteger(k + ""));
		n1 = n1.remainder(new BigInteger("9"));
		return n1.intValue() == 0 ? 9 : n1.intValue();

	}
	
	

}

/**
 * 
 * Problem Statement-
 * [Super Reduced String](https://www.hackerrank.com/challenges/reduced-string/problem) 
 * 
 */
package com.javaaid.hackerrank.solutions.algorithms.strings;

import java.util.Scanner;
import java.util.Stack;

/**
 * @author Kanahaiya Gupta
 *
 */
public class SuperReducedString {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		String s = sc.next();
		String value = getReducedString(s);
		System.out.println(value == "" ? "Empty String" : value);
		sc.close();
	}

	private static String getReducedString(String s) {
		char[] ch = s.toCharArray();
		Stack st = new Stack();
		for (int i = 0; i < ch.length; i++) {
			if (st.empty()) {
				st.push(ch[i]);

			} else if (st.peek() == ch[i]) {
				st.pop();
			} else {
				st.push(ch[i]);

			}
		}
		String str = "";
		while (!st.isEmpty()) {
			str = st.pop() + str;
		}
		return str;
	}

}

/**
 * 
 */
package com.javaaid.hackerrank.solutions.languages.java.advanced;

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.security.Permission;

/**
 * @author Kanahaiya Gupta
 *
 */
public class CanYouAccess {
	public static void main(String[] args) throws Exception {
		DoNotTerminate.forbidExit();

		try {
			BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
			int num = Integer.parseInt(br.readLine().trim());
			Object o;// Must be used to hold the reference of the instance of the class
						// Solution.Inner.Private

			// Inner i= new Inner();
			// Private p=new Private();
			/**main code starts from here*/
			CanYouAccess.Inner si = new CanYouAccess.Inner();
			o = si.new Private();
			System.out.println(num + " is " + ((CanYouAccess.Inner.Private) o).powerof2(num));
			/**main code end  here*/

			System.out.println("An instance of class: " + o.getClass().getCanonicalName() + " has been created");

		} // end of try

		catch (DoNotTerminate.ExitTrappedException e) {
			System.out.println("Unsuccessful Termination!!");
		}
	}// end of main

	static class Inner {
		private class Private {
			private String powerof2(int num) {
				return ((num & num - 1) == 0) ? "power of 2" : "not a power of 2";
			}
		}
	}// end of Inner

}// end of Solution

class DoNotTerminate { // This class prevents exit(0)

	public static class ExitTrappedException extends SecurityException {

		private static final long serialVersionUID = 1L;
	}

	public static void forbidExit() {
		final SecurityManager securityManager = new SecurityManager() {
			@Override
			public void checkPermission(Permission permission) {
				if (permission.getName().contains("exitVM")) {
					throw new ExitTrappedException();
				}
			}
		};
		System.setSecurityManager(securityManager);
	}
}

/**
 * 
 */
package com.javaaid.hackerrank.solutions.languages.java.datastructures;

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

/**
 * @author Kanahaiya Gupta
 *
 */
public class JavaMap {
	public static void main(String[] argh) {
		Scanner in = new Scanner(System.in);
		Map hmap = new HashMap();
		int n = in.nextInt();
		in.nextLine();
		for (int i = 0; i < n; i++) {
			String name = in.nextLine();
			int phone = in.nextInt();
			hmap.put(name, phone);
			in.nextLine();
		}
		while (in.hasNext()) {
			String s = in.nextLine();
			if (hmap.containsKey(s)) {
				System.out.println(s + "=" + hmap.get(s));
			} else {
				System.out.println("Not found");
			}
		}
		in.close();
	}
}

/**
 * 
 */
package com.javaaid.hackerrank.solutions.languages.java.oop;

import java.util.ArrayList;
import java.util.Scanner;

/**
 * @author Kanahaiya Gupta
 *
 */
class Student {
}

class Rockstar {
}

class Hacker {
}

public class JavaInstanceofkeyword {

	static String count(ArrayList mylist) {
		int a = 0, b = 0, c = 0;
		for (int i = 0; i < mylist.size(); i++) {
			Object element = mylist.get(i);
			if (element instanceof Student)
				a++;
			if (element instanceof Rockstar)
				b++;
			if (element instanceof Hacker)
				c++;
		}
		String ret = Integer.toString(a) + " " + Integer.toString(b) + " " + Integer.toString(c);
		return ret;
	}

	public static void main(String[] args) {
		ArrayList mylist = new ArrayList();
		Scanner sc = new Scanner(System.in);
		int t = sc.nextInt();
		for (int i = 0; i < t; i++) {
			String s = sc.next();
			if (s.equals("Student"))
				mylist.add(new Student());
			if (s.equals("Rockstar"))
				mylist.add(new Rockstar());
			if (s.equals("Hacker"))
				mylist.add(new Hacker());
		}
		System.out.println(count(mylist));
		sc.close();
	}
}

/**
 * 
 */
package com.javaaid.hackerrank.solutions.languages.java.datastructures;

/**
 * @author Kanahaiya Gupta
 *
 */
public class JavaGenerics {
	// Write your code here
	public  void printArray(T[] in) {

		for (T t : in) {
			System.out.println(t);
		}
	}
}

/**
 * 
 */
package com.javaaid.hackerrank.solutions.languages.java.bignumber;

import java.math.BigDecimal;
import java.util.Arrays;
import java.util.Collections;
import java.util.Comparator;
import java.util.Scanner;

/**
 * @author Kanahaiya Gupta
 *
 */
public class JavaBigDecimal {
	public static void main(String[] args) {
		// Input
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();
		String[] s = new String[n + 2];
		for (int i = 0; i < n; i++) {
			s[i] = sc.next();
		}
		sc.close();

		// Write your code here
		Arrays.sort(s, 0, n, Collections.reverseOrder(new Comparator() {
			public int compare(String s1, String s2) {
				BigDecimal b1 = new BigDecimal(s1);
				BigDecimal b2 = new BigDecimal(s2);
				return b1.compareTo(b2);

			}
		}));

		// Output
		for (int i = 0; i < n; i++) {
			System.out.println(s[i]);
		}
	}

}

/**
 * 
 */
package com.javaaid.hackerrank.solutions.languages.java.datastructures;

import java.util.BitSet;
import java.util.Scanner;

/**
 * @author Kanahaiya Gupta
 *
 */
public class JavaBitSet {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int N = sc.nextInt();
		int M = sc.nextInt();
		BitSet b1 = new BitSet(N);
		BitSet b2 = new BitSet(N);
		for (int i = 0; i < M; i++) {
			String op = sc.next();
			int x = sc.nextInt();
			int y = sc.nextInt();
			switch (op) {
			case "AND":
				if (x == 1) {
					b1.and(b2);
				} else {
					b2.and(b1);
				}
				break;
			case "OR":
				if (x == 1) {
					b1.or(b2);
				} else {
					b2.or(b1);
				}
				break;
			case "FLIP":
				if (x == 1) {
					b1.flip(y);
				} else {
					b2.flip(y);
				}
				break;
			case "SET":
				if (x == 1) {
					b1.set(y);
				} else {
					b2.set(y);
				}
				break;
			case "XOR":
				if (x == 1) {
					b1.xor(b2);
				} else {
					b2.xor(b1);
				}
				break;
			}
			System.out.println(b1.cardinality() + " " + b2.cardinality());

		}
		sc.close();
	}
}

/**
 * 
 * Problem Statement-
 * [Trees: Is This a Binary Search Tree?](https://www.hackerrank.com/challenges/ctci-is-binary-search-tree/problem)  
 * 
 */
package com.javaaid.hackerrank.solutions.tutorials.ctci;

/**
 * @author Kanahaiya Gupta
 *
 */
public class TreesIsThisABinarySearchTree {
	static class Node {
		int data;
		Node left;
		Node right;

		Node(int data) {
			this.data = data;
		}
	}

	boolean checkBST(Node root) {
		return checkBSTUtil(root, Integer.MIN_VALUE, Integer.MAX_VALUE);
	}

	/**
	 * @param root
	 * @param minValue
	 * @param maxValue
	 * @return
	 */
	private boolean checkBSTUtil(Node root, int minValue, int maxValue) {
		if (root == null)
			return true;
		return (root.data > minValue && root.data < maxValue && checkBSTUtil(root.left, minValue, root.data)&& checkBSTUtil(root.right, root.data, maxValue));
	}

}

/**
 * 
 * Problem Statement-
 * [Bit Manipulation: Lonely Integer](https://www.hackerrank.com/challenges/ctci-lonely-integer/problem)
 * 
 */
package com.javaaid.hackerrank.solutions.tutorials.ctci;

import java.util.Scanner;

/**
 * @author Kanahaiya Gupta
 *
 */
public class LonelyInteger {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();
		int res = 0;
		for (int i = 0; i < n; i++) {
			res ^= sc.nextInt();
		}
		System.out.println(res);
		sc.close();
	}
}

/**
 * 
 */
package com.javaaid.hackerrank.solutions.languages.java.advanced;

import java.util.ArrayList;
import java.util.Scanner;

/**
 * @author Kanahaiya Gupta
 *
 */

enum Color {
	RED, GREEN
}

abstract class Tree {

	private int value;
	private Color color;
	private int depth;

	public Tree(int value, Color color, int depth) {
		this.value = value;
		this.color = color;
		this.depth = depth;
	}

	public int getValue() {
		return value;
	}

	public Color getColor() {
		return color;
	}

	public int getDepth() {
		return depth;
	}

	public abstract void accept(TreeVis visitor);
}

class TreeNode extends Tree {

	private ArrayList children = new ArrayList<>();

	public TreeNode(int value, Color color, int depth) {
		super(value, color, depth);
	}

	public void accept(TreeVis visitor) {
		visitor.visitNode(this);

		for (Tree child : children) {
			child.accept(visitor);
		}
	}

	public void addChild(Tree child) {
		children.add(child);
	}
}

class TreeLeaf extends Tree {

	public TreeLeaf(int value, Color color, int depth) {
		super(value, color, depth);
	}

	public void accept(TreeVis visitor) {
		visitor.visitLeaf(this);
	}
}

abstract class TreeVis {
	public abstract int getResult();

	public abstract void visitNode(TreeNode node);

	public abstract void visitLeaf(TreeLeaf leaf);

}

class SumInLeavesVisitor extends TreeVis {
	private int result = 0;

	public int getResult() {
		return result;
	}

	public void visitNode(TreeNode node) {
		// do nothing
	}

	public void visitLeaf(TreeLeaf leaf) {
		result += leaf.getValue();
	}
}

class ProductOfRedNodesVisitor extends TreeVis {
	private long result = 1;
	private final int M = 1000000007;

	public int getResult() {
		return (int) result;
	}

	public void visitNode(TreeNode node) {
		if (node.getColor() == Color.RED) {
			result = (result * node.getValue()) % M;
		}
	}

	public void visitLeaf(TreeLeaf leaf) {
		if (leaf.getColor() == Color.RED) {
			result = (result * leaf.getValue()) % M;
		}
	}
}

class FancyVisitor extends TreeVis {
	private int nonLeafEvenDepthSum = 0;
	private int greenLeavesSum = 0;

	public int getResult() {
		return Math.abs(nonLeafEvenDepthSum - greenLeavesSum);
	}

	public void visitNode(TreeNode node) {
		if (node.getDepth() % 2 == 0) {
			nonLeafEvenDepthSum += node.getValue();
		}
	}

	public void visitLeaf(TreeLeaf leaf) {
		if (leaf.getColor() == Color.GREEN) {
			greenLeavesSum += leaf.getValue();
		}
	}
}

public class JavaVisitorPattern {
	static int[] values;
	static Color[] colors;
	static ArrayList[] edges;
	// each edges[i] holds arrayList of all nodes connnected to node i

	@SuppressWarnings("unchecked")
	public static Tree solve() {
		int n;
		TreeNode root;
		Scanner sc = new Scanner(System.in);

		n = sc.nextInt();
		values = new int[n];
		colors = new Color[n];
		for (int i = 0; i < n; i++)
			values[i] = sc.nextInt();
		for (int i = 0; i < n; i++)
			colors[i] = sc.nextInt() == 0 ? Color.RED : Color.GREEN;

		// initialize arraylists
		edges = (ArrayList[]) new ArrayList[n + 1];
		for (int i = 1; i <= n; i++)
			edges[i] = new ArrayList();

		// read the n- 1 edges and store them in both directions
		for (int i = 0; i < n - 1; i++) {
			int edgeNode1 = sc.nextInt();
			int edgeNode2 = sc.nextInt();
			edges[edgeNode1].add(edgeNode2);
			edges[edgeNode2].add(edgeNode1);
		}
		sc.close();
		root = new TreeNode(values[0], colors[0], 0); // root is always internal
		addChildren(root, 1);
		return root;
	}

	public static void addChildren(Tree node, Integer nodeNumber) {
		// for all edges coming out of this node
		for (Integer otherNodeNumber : edges[nodeNumber]) {
			Tree otherNode;
			if (edges[otherNodeNumber].size() > 1)
				// new internal node
				otherNode = new TreeNode(values[otherNodeNumber - 1], colors[otherNodeNumber - 1], node.getDepth() + 1);
			else
				// new leaf
				otherNode = new TreeLeaf(values[otherNodeNumber - 1], colors[otherNodeNumber - 1], node.getDepth() + 1);
			((TreeNode) node).addChild(otherNode);
			edges[otherNodeNumber].remove(nodeNumber); // remove reverse edge
			if (otherNode instanceof TreeNode)
				addChildren(otherNode, otherNodeNumber);
		}
	}

	public static void main(String[] args) {
		Tree root = solve();
		SumInLeavesVisitor vis1 = new SumInLeavesVisitor();
		ProductOfRedNodesVisitor vis2 = new ProductOfRedNodesVisitor();
		FancyVisitor vis3 = new FancyVisitor();

		root.accept(vis1);
		root.accept(vis2);
		root.accept(vis3);

		int res1 = vis1.getResult();
		int res2 = vis2.getResult();
		int res3 = vis3.getResult();

		System.out.println(res1);
		System.out.println(res2);
		System.out.println(res3);
	}
}

/**
 * 
 * Problem Statement-
 * [Closest Numbers](https://www.hackerrank.com/challenges/closest-numbers/problem)
 * 
 */
package com.javaaid.hackerrank.solutions.algorithms.sorting;

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

/**
 * @author Kanahaiya Gupta
 *
 */
public class ClosestNumbers {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int t = sc.nextInt();
		int a[] = new int[t];
		for (int i = 0; i < t; i++) {
			a[i] = sc.nextInt();
		}
		Arrays.sort(a);
		int minDiff = Integer.MAX_VALUE;
		int min1 = 0;
		int min2 = 0, minIndex = -1;

		String result = "";
		for (int i = 1; i < t; i++) {
			int diff = Math.abs(a[i] - a[i - 1]);
			if (diff < minDiff) {
				minDiff = diff;
				min1 = a[i - 1];
				min2 = a[i];
				minIndex = i;
				result = min1 + " " + min2;
			}
		}
		for (int i = minIndex + 1; i < t; i++) {
			if (minDiff == Math.abs(a[i] - a[i - 1])) {
				result = result + " " + a[i - 1] + " " + a[i];
			}
		}
		System.out.println(result);
		sc.close();
	}
}

/**
 * 
 */
package com.javaaid.hackerrank.solutions.languages.java.strings;

import java.util.ArrayList;
import java.util.Collections;
import java.util.Scanner;

/**
 * @author Kanahaiya Gupta
 *
 */
public class JavaSubstringComparisons {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		ArrayList list = new ArrayList();
		String s = sc.next();
		int k = sc.nextInt();
		for (int i = 0; i <= s.length() - k; i++) {
			String tmp = s.substring(i, k + i);
			list.add(tmp);
		}
		Collections.sort(list);
		System.out.println(list.get(0));
		System.out.println(list.get(list.size() - 1));
		sc.close();
	}
}

/**
 * 
 * Problem Statement-
 * [Mars Exploration](https://www.hackerrank.com/challenges/mars-exploration/problem)  
 * 
 */
package com.javaaid.hackerrank.solutions.algorithms.strings;

import java.util.Scanner;

/**
 * @author Kanahaiya Gupta
 *
 */
public class MarsExploration {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		String s = sc.next();
		int l = s.length();
		String tmp = "SOS";
		int n = l / 3;
		String newString = tmp;
		for (int i = 1; i < n; i++) {
			newString += tmp;
		}
		int count = 0;
		for (int i = 0; i < l; i++) {
			if (newString.charAt(i) != s.charAt(i)) {
				count++;
			}
		}
		System.out.println(count);
		sc.close();
	}
}

/**
 * 
 * Problem Statement-
 * [Sparse Arrays](https://www.hackerrank.com/challenges/sparse-arrays/problem)    
 * [Tutorial](https://youtu.be/BZdnvTBO4vI)
 */
package com.javaaid.hackerrank.solutions.datastructures.arrays;

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

/**
 * @author Kanahaiya Gupta
 *
 */
public class SparseArrays {

	static int[] matchingStrings(String[] strings, String[] queries) {
		Map map = new HashMap<>();
		int result[] = new int[queries.length];

		for (int i = 0; i < strings.length; i++) {
			String inputString = strings[i];
			if (map.containsKey(inputString)) {
				map.put(inputString, map.get(inputString) + 1);
			} else {
				map.put(inputString, 1);
			}
		}

		for (int i = 0; i < queries.length; i++) {
			String queryString = queries[i];
			if (map.containsKey(queryString)) {
				result[i] = map.get(queryString);
			}
		}

		return result;
	}

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int noOfStrings = sc.nextInt();

		String str[] = new String[noOfStrings];

		for (int i = 0; i < noOfStrings; i++) {
			str[i] = sc.next();
		}
		int queries = sc.nextInt();
		String strQ[] = new String[queries];

		for (int i = 0; i < queries; i++) {
			strQ[i] = sc.next();
		}
		int[] counter = matchingStrings(str, strQ);
		System.out.println(Arrays.toString(counter));
		sc.close();
	}

}

/**
 * 
 * Problem Statement-
 * [Scope](https://www.hackerrank.com/challenges/30-scope/problem)        
 * 
 */
package com.javaaid.hackerrank.solutions.thirtydaysofcode;

/**
 * @author Kanahaiya Gupta
 *
 */
public class Day14Scope {

	/**
	 * 
	 * @param elements
	 
Difference(int [] elements){
    this.elements=elements;
}
    
 void computeDifference() {
		int maxNum = elements[0];
		int minNum = maxNum;
		for (int i = 1; i < elements.length; i++) {
			
			maxNum=elements[i]>maxNum?elements[i]:maxNum;
			minNum=elements[i]>minNum?minNum:elements[i];
			
		}
		maximumDifference=Math.abs(maxNum-minNum);
	}
	*/
}

/**
 * 
 */
package com.javaaid.hackerrank.solutions.languages.java.strings;

import java.util.Scanner;
import java.util.regex.Matcher;
import java.util.regex.Pattern;

/**
 * @author Kanahaiya Gupta
 *
 */
public class TagContentExtractor {
	public static void main(String[] args) {

		Scanner in = new Scanner(System.in);
		int testCases = Integer.parseInt(in.nextLine());
		while (testCases > 0) {
			String line = in.nextLine();
			String regex = "<(.+)>([^<>]+)()";
			Pattern p = Pattern.compile(regex);
			Matcher m = p.matcher(line);
			int counter = 0;
			while (m.find()) {
				if (m.group(2).length() != 0) {
					System.out.println(m.group(2));
					counter++;
				}

			}
			if (counter == 0)
				System.out.println("None");
			testCases--;
		}
		in.close();
	}
}

/**
 * 
 */
package com.javaaid.hackerrank.solutions.languages.java.advanced;

/**
 * @author Kanahaiya Gupta
 *
 */
public class CovariantReturnTypes {
/**
 * main code starts from here** */
	class Flower{
	    
	    public String whatsYourName(){
	        return "I have many names and types.";
	    }
	}
	class Jasmine extends Flower{
	    public String whatsYourName(){
	        return "Jasmine";
	    }
	}
	class Lily extends Flower{
	    public String whatsYourName(){
	        return "Lily";
	    }
	}
	class Lotus extends Flower{
	    public String whatsYourName(){
	        return "Lotus";
	    }
	}
	class State{
	    Flower yourNationalFlower(){
	        return new Flower();
	    }
	}
	class WestBengal extends State{
	    Jasmine yourNationalFlower(){
	        return new Jasmine();
	    }
	}
	class Karnataka extends State{
	    Lotus yourNationalFlower(){
	        return new Lotus();
	    }
	}
	class AndhraPradesh extends State{
	    Lily yourNationalFlower(){
	        return new Lily();
	    }
	    /**
	     * main code ends here  */
	}
}

package com.javaaid.hackerrank.solutions.languages.java.introduction;

import java.util.Scanner;

/**
 * 
 * @author Kanahaiya Gupta
 *
 */
public class JavaStdinAndStdoutII {

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int i = sc.nextInt();
		double d = sc.nextDouble();
		sc.nextLine();
		String s = sc.nextLine();
		sc.close();
		System.out.println("String: " + s);
		System.out.println("Double: " + d);
		System.out.println("Int: " + i);
	}
}

/**
 * 
 * Problem Statement-
 * [Sorting](https://www.hackerrank.com/challenges/30-sorting/problem)  
 * 
 */
package com.javaaid.hackerrank.solutions.thirtydaysofcode;

import java.util.Scanner;

/**
 * @author Kanahaiya Gupta
 *
 */
public class Day20Sorting {
	public static void main(String[] args) {
		Scanner in = new Scanner(System.in);
		int n = in.nextInt();
		int a[] = new int[n];
		for (int a_i = 0; a_i < n; a_i++) {
			a[a_i] = in.nextInt();
		}
		in.close();
		int count = 0;
		boolean swapped = true;
		for (int j = a.length - 1; (j >= 0 && swapped); j--) {
			swapped = false;
			for (int k = 0; k < j; k++) {

				if (a[k] > a[k + 1]) {
					int temp = a[k];
					count++;
					a[k] = a[k + 1];
					a[k + 1] = temp;
					swapped = true;
				}
			}
		}
		System.out.println("Array is sorted in " + count + " swaps.");
		System.out.println("First Element: " + a[0]);
		System.out.println("Last Element: " + a[a.length - 1]);

	}
}

/**
 * 
 * Problem Statement-
 * [Beautiful Binary String](https://www.hackerrank.com/challenges/beautiful-binary-string/problem)
 * 
 */
package com.javaaid.hackerrank.solutions.algorithms.strings;

import java.util.Scanner;

/**
 * @author Kanahaiya Gupta
 *
 */
public class BeautifulBinaryString {
	 static int minSteps(int n, String strB){
	        int stepsCount=0;
	        String tmpStr=strB;
	        while(tmpStr.indexOf("010")!=-1){
	        	tmpStr=tmpStr.replaceFirst("010", "011");
	        	stepsCount++;
	        }
	        return stepsCount;
	    }

	    public static void main(String[] args) {
	        Scanner in = new Scanner(System.in);
	        int n = in.nextInt();
	        String B = in.next();
	        int result = minSteps(n, B);
	        System.out.println(result);
	        in.close();
	    }
	}

/**
 * 
 * Problem Statement-
 * [New Year Chaos](https://www.hackerrank.com/challenges/new-year-chaos/problem) 
 * [Tutorial](https://youtu.be/YWYF6bOhPW8)
 */

package com.javaaid.hackerrank.solutions.algorithms.com.constructive_algorithms;

import java.util.Scanner;

public class NewYearChaos {

	private static void minimumBribes(int[] arr) {
		int swapCount = 0;

		for (int i = arr.length - 1; i >= 0; i--) {

			if (arr[i] != i + 1) { // filter cases, when you do not bribe, be at the ith position wherever you are

				if (((i - 1) >= 0) && arr[i - 1] == (i + 1)) { // 1)Being at initial ith position, valid current
																// position after given bribe can be (i-1)th position
					swapCount++;
					swap(arr, i, i - 1);
				} else if (((i - 2) >= 0) && arr[i - 2] == (i + 1)) { // 2)Being at initial ith position, valid current
																		// position after given bribes can be (i-2)th
																		// position
					swapCount += 2;
					swap(arr, i - 2, i - 1);
					swap(arr, i - 1, i);
				} else { // 3)Too chaotic (trying to bribe more than 2 people which is ahead of you)
					System.out.println("Too chaotic");
					return;
				}
			}

		}
		System.out.println(swapCount);

	}

	private static void swap(int[] arr, int a, int b) {
		int temp = arr[a];
		arr[a] = arr[b];
		arr[b] = temp;
	}

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int t = sc.nextInt();
		while (t-- > 0) {
			int n = sc.nextInt();
			int a[] = new int[n];
			for (int i = 0; i < n; i++) {
				a[i] = sc.nextInt();
			}
			minimumBribes(a);
		}
		sc.close();
	}

}

/**
 * 
 * Problem Statement-
 * [Mark and Toys](https://www.hackerrank.com/challenges/mark-and-toys/problem)
 * 
 */
package com.javaaid.hackerrank.solutions.algorithms.sorting;

import java.util.Arrays;
import java.util.Scanner;
import java.io.*;
/**
 * @author Kanahaiya Gupta
 *
 */
public class MarkAndToys 
{
	public static void main(String[] args)throws IOException
	{
		Scanner in = new Scanner(System.in);
		int n = in.nextInt();
		int k = in.nextInt();
		int prices[] = new int[n];
		int i,j;
		for (i = 0; i < n; i++)
		{	
			prices[i] = in.nextInt();
		}
		j=maximumToys(prices,k);
		System.out.println(j);
	}
	public static int maximumToys(int[] prices,int k)
	{
		int n=prices.length;
		Arrays.sort(prices);
		//main programming
    		int toyCount,i,sum;
		sum=toyCount= 0;
		for (i = 0; i < n; i++) 
		{
			sum += prices[i];
			if (sum <= k) 
			{
				toyCount++;
			} 
			else 
			{
				break;
			}
		}
		return toyCount;
	}
}

/**
 * 
 */
package com.javaaid.hackerrank.solutions.languages.java.datastructures;

import java.util.Scanner;

/**
 * @author Kanahaiya Gupta
 *
 */
public class Java1DArray {
	public static void main(String[] args) {

		Scanner scan = new Scanner(System.in);
		int n = scan.nextInt();
		 // Declare array a here
        int a[]=new int[n];
        for(int i = 0 ; i < n; i++){
            int val = scan.nextInt();
            a[i]=val;
            // Fill array a here
        }
        scan.close();
        // Prints each sequential element in array a
        for (int i = 0; i < a.length; i++) {
            System.out.println(a[i]);
        }
    }
}

/**
 * 
 * Problem Statement-
 * [Mark and Toys](https://www.hackerrank.com/challenges/mark-and-toys/problem)  
 * 
 */
package com.javaaid.hackerrank.solutions.algorithms.greedy;

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

/**
 * @author Kanahaiya Gupta
 *
 */
public class MarkAndToys {
	public static void main(String[] args) {
		Scanner in = new Scanner(System.in);
		int n = in.nextInt();
		int K = in.nextInt();
		int a[] = new int[n];
		for (int i = 0; i < n; i++) {
			a[i] = in.nextInt();
		}
		Arrays.sort(a);
		int toyCount = 0, sum = 0;
		for (int i = 0; i < a.length; i++) {
			sum += a[i];
			if (sum <= K) {
				toyCount++;
			} else {
				break;
			}
		}
		System.out.println(toyCount);
		in.close();
	}
}

/**
 * 
 */
package com.javaaid.hackerrank.solutions.languages.java.datastructures;

import java.util.Comparator;
import java.util.PriorityQueue;
import java.util.Scanner;

/**
 * @author Kanahaiya Gupta
 *
 */


public class JavaPriorityQueue {
	static class Student {
		private int token;
		private String fname;
		private double cgpa;

		public Student(int id, String fname, double cgpa) {
			super();
			this.token = id;
			this.fname = fname;
			this.cgpa = cgpa;
		}

		public int getToken() {
			return token;
		}

		public String getFname() {
			return fname;
		}

		public double getCgpa() {
			return cgpa;
		}
	}

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int t = sc.nextInt();
		PriorityQueue data = new PriorityQueue(new Comparator() {
			@Override
			public int compare(Student o1, Student o2) {
				if (o1.getCgpa() < o2.getCgpa()) {
					return 1;
				} else if (o1.getCgpa() > o2.getCgpa()) {
					return -1;
				} else {
					if (o1.getFname().compareTo(o2.getFname()) == 0) {
						if (o1.getToken() > o2.getToken()) {
							return 1;
						} else if (o1.getToken() < o2.getToken()) {
							return -1;
						} else {
							return 0;
						}

					} else {
						return o1.getFname().compareTo(o2.getFname());
					}
				}
			}
		});
		for (int i = 0; i < t; i++) {
			String op = sc.next();
			switch (op) {
			case "ENTER":
				String name = sc.next();
				double cgpa = sc.nextDouble();
				int id = sc.nextInt();
				Student s = new Student(id, name, cgpa);
				data.add(s);
				break;
			case "SERVED":
				if (data.isEmpty()) {
					break;
				}
				data.remove();

			}
		}
		if (data.isEmpty())
			System.out.println("EMPTY");
		else {
			while (!data.isEmpty()) {
				Student st = data.poll();
				System.out.println(st.getFname());
			}
		}
		sc.close();
	}
}

/**
 * 
 */
package com.javaaid.hackerrank.solutions.languages.java.strings;

import java.util.Scanner;

/**
 * @author Kanahaiya Gupta
 *
 */
public class JavaStringReverse {
	public static void main(String[] args) {

		Scanner sc = new Scanner(System.in);
		String A = sc.next();
		sc.close();
		boolean found = true;
		for (int i = 0; i < A.length() / 2; i++) {
			if (A.charAt(i) != A.charAt(A.length() - 1 - i)) {
				found = false;
				break;
			}
		}
		System.out.println(found ? "Yes" : "No");
	}
}

/**
 * 
 */
package com.javaaid.hackerrank.solutions.languages.java.oop;

import java.util.Scanner;

/**
 * @author Kanahaiya Gupta
 *
 */
abstract class Book {
	String title;

	abstract void setTitle(String s);

	String getTitle() {
		return title;
	}
}

// Write MyBook class here
class MyBook extends Book {

	void setTitle(String s) {
		super.title = s;
	}
}

public class JavaAbstractClass {
	public static void main(String[] args) {
		// Book new_novel=new Book(); This line prHMain.java:25: error: Book is
		// abstract; cannot be instantiated
		Scanner sc = new Scanner(System.in);
		String title = sc.nextLine();
		MyBook new_novel = new MyBook();
		new_novel.setTitle(title);
		System.out.println("The title is: " + new_novel.getTitle());
		sc.close();

	}
}

/**
 * 
 */
package com.javaaid.hackerrank.solutions.languages.java.datastructures;

import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;

/**
 * @author Kanahaiya Gupta
 *
 */
public class JavaList {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();
		List L = new ArrayList();
		for (int i = 0; i < n; i++) {
			L.add(sc.nextInt());
		}
		int Q = sc.nextInt();
		for (int i = 0; i < Q; i++) {
			String op = sc.next();
			if (op.equalsIgnoreCase("INSERT")) {
				int index = sc.nextInt();
				int item = sc.nextInt();
				L.add(index, item);
			} else {
				L.remove(sc.nextInt());
			}

		}
		for (Integer integer : L) {
			System.out.print(integer + " ");
		}
		sc.close();
	}
}

/**
 * 
 * Problem Statement-
 * [Delete duplicate-value nodes from a sorted linked list](https://www.hackerrank.com/challenges/delete-duplicate-value-nodes-from-a-sorted-linked-list/problem)  
 * 
 */
package com.javaaid.hackerrank.solutions.datastructures.linkedlists;

/**
 * @author Kanahaiya Gupta
 *
 */
public class DeleteDuplicateValueNodesFromASortedLinkedList {
	class Node {
		int data;
		Node next;
	}

	Node RemoveDuplicates(Node head) {
		Node current = head;
		
		while (current.next != null) {
			if (current.data == current.next.data) {
				current.next = current.next.next;
				continue;
			} else {
				current = current.next;
			}
		}
		return head;
	}
}

/**
 * 
 * Problem Statement-
 * [Linked Lists: Detect a Cycle](https://www.hackerrank.com/challenges/ctci-linked-list-cycle/problem) 
 * 
 */
package com.javaaid.hackerrank.solutions.tutorials.ctci;

/**
 * @author Kanahaiya Gupta
 *
 */
public class DetectACycle {
	class Node {
		int data;
		Node next;
	}

	boolean hasCycle(Node head) {
		Node p1 = head, p2 = head;

		while (p1 != null && p1.next != null && p2 != null) {
			p1 = p1.next;
			p2 = p2.next.next;
			{
				if (p1 == p2)
					return true;

			}

		}
		return false;

	}

}

/**
 * 
 * Problem Statement-
 * [Insert a Node at the Tail of a Linked List](https://www.hackerrank.com/challenges/insert-a-node-at-the-tail-of-a-linked-list)
 * 
 */
package com.javaaid.hackerrank.solutions.datastructures.linkedlists;

/**
 * @author Kanahaiya Gupta
 *
 */
public class InsertANodeAtTheTailOfALinkedList {
	class Node {
		int data;
		Node next;
	}

	Node Insert(Node head, int data) {
		Node current = head;
		Node newNode = new Node();
		newNode.data = data;
		newNode.next = null;

		while (current.next != null) {
			current = current.next;
		}
		current.next = newNode;

		return head;
	}

}

/**
 * 
 * Problem Statement-
 * [Lonely Integer](https://www.hackerrank.com/challenges/lonely-integer/problem)
 * [Tutorial](https://youtu.be/k1i6eIpeXak)
 * 
 */
package com.javaaid.hackerrank.solutions.algorithms.bitmanipulation;

import java.util.Scanner;

/**
 * @author Kanahaiya Gupta
 *
 */
public class LonelyInteger {
	static int lonelyinteger(int[] a) {
		int result = 0;
		for (int i = 0; i < a.length; i++) {
			result ^= a[i];

		}

		return result;
	}

	public static void main(String[] args) {
		Scanner in = new Scanner(System.in);
		int res;

		int _a_size = Integer.parseInt(in.nextLine());
		int[] _a = new int[_a_size];
		int _a_item;
		String next = in.nextLine();
		String[] next_split = next.split(" ");

		for (int _a_i = 0; _a_i < _a_size; _a_i++) {
			_a_item = Integer.parseInt(next_split[_a_i]);
			_a[_a_i] = _a_item;
		}

		res = lonelyinteger(_a);
		System.out.println(res);
		in.close();
	}
}

/**
 * 
 * Problem Statement-
 * [Maximum Element](https://www.hackerrank.com/challenges/maximum-element)    
 * [Tutorial] (https://youtu.be/CXYL8JfeN6I)
 */
package com.javaaid.hackerrank.solutions.datastructures.stacks;

import java.util.Scanner;
import java.util.Stack;

/**
 * 
 * @author Kanahaiya Gupta
 *
 */
public class MaximumElement {

	public static void main(String[] args) {

		Scanner sc = new Scanner(System.in);
		int N = sc.nextInt();

		Stack mainStack = new Stack<>();
		Stack maxStack = new Stack<>();
		maxStack.push(Integer.MIN_VALUE);

		for (int i = 0; i < N; i++) {
			int op = sc.nextInt();
			switch (op) {
			case 1:
				int item = sc.nextInt();
				mainStack.push(item);
				int maxSoFar = maxStack.peek();
				if (item > maxSoFar) {
					maxStack.push(item);
				} else {
					maxStack.push(maxSoFar);
				}
				break;
			case 2:
				mainStack.pop();
				maxStack.pop();
				break;

			case 3:

				System.out.println(maxStack.peek());
				break;
			}
		}
		sc.close();
	}
}

/**
 * 
 */
package com.javaaid.hackerrank.solutions.languages.java.bignumber;

import java.math.BigInteger;
import java.util.Scanner;

/**
 * @author Kanahaiya Gupta
 *
 */
public class JavaPrimalityTest {

	public static void main(String[] args) {
		Scanner in = new Scanner(System.in);
		BigInteger n = in.nextBigInteger();
		in.close();
		System.out.println(n.isProbablePrime(100) ? "prime" : "not prime");
	}
}

/**
 * 
 * Problem Statement-
 * [Big Sorting](https://www.hackerrank.com/challenges/big-sorting/problem)  
 * 
 */
package com.javaaid.hackerrank.solutions.algorithms.strings;

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

/**
 * @author Kanahaiya Gupta
 *
 */
public class BigSorting {
	public static void main(String[] args) {
		Scanner in = new Scanner(System.in);
		int n = in.nextInt();
		String[] unsorted = new String[n];
		for (int unsorted_i = 0; unsorted_i < n; unsorted_i++) {
			unsorted[unsorted_i] = in.next();
		}

		Arrays.sort(unsorted, new Comparator() {

			public int compare(String s1, String s2) {
				return compareStrings(s1, s2);
			}
		});
		printArray(unsorted);
		in.close();
	}

	private static int compareStrings(String s1, String s2) {
		if (s1.length() < s2.length()) {
			return -1;
		} else if (s1.length() > s2.length()) {
			return 1;
		}
		for (int k = 0; k < s1.length(); k++) {
			if ((int) s1.charAt(k) < (int) s2.charAt(k))
				return -1;
			if ((int) s1.charAt(k) > (int) s2.charAt(k))
				return 1;

		}
		return 0;

	}

	private static void printArray(String[] unsorted) {

		for (String string : unsorted) {
			System.out.println(string);
		}

	}

}

/**
 * 
 * Problem Statement-
 * [Level Order Traversal](https://www.hackerrank.com/challenges/tree-level-order-traversal/problem)   
 * 
 */
package com.javaaid.hackerrank.solutions.datastructures.trees;

import java.util.LinkedList;
import java.util.Queue;

/**
 * @author Kanahaiya Gupta
 *
 */
public class LevelOrderTraversal {
	class Node {
		int data;
		Node left;
		Node right;
	}

	void levelOrder(Node root) {

		Queue q = new LinkedList();
		q.add(root);

		while (!q.isEmpty()) {

			Node currentNode = q.poll();
			System.out.print(currentNode.data + " ");
			if (currentNode.left != null)
				q.add(currentNode.left);
			if (currentNode.right != null)
				q.add(currentNode.right);
		}

	}
}

/**
 * 
 * Problem Statement-
 * [Sorting: Comparator](https://www.hackerrank.com/challenges/ctci-comparator-sorting/problem)  
 * 
 */
package com.javaaid.hackerrank.solutions.tutorials.ctci;

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

/**
 * @author Kanahaiya Gupta
 *
 */

// Write your Checker class here
class Checker implements Comparator {
	public int compare(Player p1, Player p2) {
		if (p1.score > p2.score)
			return -1;
		if (p1.score < p2.score)
			return 1;
		return p1.name.compareTo(p2.name);
	}
}

class Player {
	String name;
	int score;

	Player(String name, int score) {
		this.name = name;
		this.score = score;
	}
}

class SortingComparator {

	public static void main(String[] args) {
		Scanner scan = new Scanner(System.in);
		int n = scan.nextInt();

		Player[] player = new Player[n];
		Checker checker = new Checker();

		for (int i = 0; i < n; i++) {
			player[i] = new Player(scan.next(), scan.nextInt());
		}
		scan.close();

		Arrays.sort(player, checker);
		for (int i = 0; i < player.length; i++) {
			System.out.printf("%s %s\n", player[i].name, player[i].score);
		}
	}
}

/**
 * 
 * Problem Statement-
 * [Big Sorting](https://www.hackerrank.com/challenges/big-sorting/problem)    
 * 
 */
package com.javaaid.hackerrank.solutions.datastructures.arrays;

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

/**
 * @author Kanahaiya Gupta
 *
 */
public class BigSorting {
	public static void main(String[] args) {
		Scanner in = new Scanner(System.in);
		int n = in.nextInt();
		String[] unsorted = new String[n];
		for (int unsorted_i = 0; unsorted_i < n; unsorted_i++) {
			unsorted[unsorted_i] = in.next();
		}

		Arrays.sort(unsorted, new Comparator() {

			public int compare(String s1, String s2) {
				return compareStrings(s1, s2);
			}
		});
		printArray(unsorted);
		in.close();
	}

	private static int compareStrings(String s1, String s2) {
		if (s1.length() < s2.length()) {
			return -1;
		} else if (s1.length() > s2.length()) {
			return 1;
		}
		for (int k = 0; k < s1.length(); k++) {
			if ((int) s1.charAt(k) < (int) s2.charAt(k))
				return -1;
			if ((int) s1.charAt(k) > (int) s2.charAt(k))
				return 1;

		}
		return 0;

	}

	private static void printArray(String[] unsorted) {

		for (String string : unsorted) {
			System.out.println(string);
		}

	}

}

/**
 * 
 */
package com.javaaid.hackerrank.solutions.languages.java.advanced;

import java.lang.reflect.Method;
import java.util.ArrayList;
import java.util.Collections;

/**
 * @author Kanahaiya Gupta
 *
 */

class Student {
	private String name;
	private String id;
	private String email;

	public String getName() {
		return name;
	}

	public void setId(String id) {
		this.id = id;
	}

	public void setEmail(String email) {
		this.email = email;
	}

	public void anothermethod() {
	}
}

public class JavaReflectionAttributes {
	public static void main(String[] args) {
		Class student = new Student().getClass();
		Method[] methods = student.getDeclaredMethods();
		ArrayList methodList = new ArrayList<>();
		for (Method m : methods) {
			methodList.add(m.getName());
		}
		Collections.sort(methodList);
		for (String name : methodList) {
			System.out.println(name);
		}
	}

}

/**
 * 
 * Problem Statement-
 * [Balanced Brackets](https://www.hackerrank.com/challenges/balanced-brackets)    
 * 
 */
package com.javaaid.hackerrank.solutions.datastructures.stacks;

import java.util.Scanner;
import java.util.Stack;

/**
 * @author Kanahaiya Gupta
 *
 */
public class BalancedBrackets {
	private static String matchParenthisis(String str) {
		Stack st = new Stack ();
		char[] ch = str.toCharArray();
		for (char c : ch) {

			if (c == '{' || c == '[' || c == '(') {
				st.push(c);
			} else {

				if (c == ']' && !st.isEmpty() && st.pop() == '[') {
					continue;

				} else if (c == '}' && !st.isEmpty() && st.pop() == '{') {
					continue;
				} else if (c == ')' && !st.isEmpty() && st.pop() == '(') {
					continue;
				} else {
					return "NO";
				}

			}
		}
		if (!st.isEmpty()) {
			return "NO";
		}

		return "YES";

	}

	public static void main(String[] args) {
		Scanner in = new Scanner(System.in);
		int t = in.nextInt();
		for (int a0 = 0; a0 < t; a0++) {
			String s = in.next();
			System.out.println(matchParenthisis(s));
		}
		in.close();
	}
}

/**
 * 
 * Problem Statement-
 * [Postorder Traversal](https://www.hackerrank.com/challenges/tree-postorder-traversal)   
 * 
 */
package com.javaaid.hackerrank.solutions.datastructures.trees;

/**
 * @author Kanahaiya Gupta
 *
 */
public class PostorderTraversal {
	class Node {
		int data;
		Node left;
		Node right;
	}

	void postOrder(Node root) {
		if (root != null) {
			postOrder(root.left);
			postOrder(root.right);
			System.out.print(root.data + " ");

		}
	}
}

/**
 * 
 * Problem Statement-
 * [Find the Median](https://www.hackerrank.com/challenges/find-the-median/problem) 
 * 
 */
package com.javaaid.hackerrank.solutions.algorithms.sorting;

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

/**
 * @author Kanahaiya Gupta
 *
 */
public class FindTheMedian {

	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 n = sc.nextInt();
		int a[] = new int[n];
		for (int i = 0; i < n; i++)
			a[i] = sc.nextInt();
		Arrays.sort(a);
		if ((n & 1) == 1) {
			System.out.println(a[n / 2]);
		} else {
			System.out.println((a[n / 2] + a[n / 2 + 1]) / 2);
		}
		sc.close();
	}
}

/**
 * 
 * Problem Statement-
 * [Top View](https://www.hackerrank.com/challenges/tree-top-view/problem)   
 * 
 */
package com.javaaid.hackerrank.solutions.datastructures.trees;

/**
 * @author Kanahaiya Gupta
 *
 */
public class TopView {
	class Node {
		int data;
		Node left;
		Node right;
	}

	void topView(Node root) {
		Node rootNode = root;

		if (rootNode == null)
			return;
		printLeft(rootNode.left);
		System.out.print(rootNode.data + " ");
		printright(rootNode.right);

	}

	void printLeft(Node rootNode) {
		if (rootNode == null)
			return;
		printLeft(rootNode.left);
		System.out.print(rootNode.data + " ");
	}

	void printright(Node rootNode) {
		if (rootNode == null)
			return;
		System.out.print(rootNode.data + " ");
		printright(rootNode.right);

	}

}

/**
 * 
 */
package com.javaaid.hackerrank.solutions.languages.java.introduction;

import java.util.Scanner;

/**
 * @author Kanahaiya Gupta
 *
 */
public class JavaLoopsII {
	public static void main(String[] argh) {
		Scanner in = new Scanner(System.in);
		int t = in.nextInt();
		for (int i = 0; i < t; i++) {
			int a = in.nextInt();
			int b = in.nextInt();
			int n = in.nextInt();
			int temp = a;
			for (int j = 0; j < n; j++) {
				temp += (Math.pow(2, j) * b);
				System.out.print(temp + " ");
			}
			System.out.println();
		}
		in.close();
	}
}

/**
 * 
 * Problem Statement-
 * [Print in Reverse](https://www.hackerrank.com/challenges/print-the-elements-of-a-linked-list-in-reverse/problem) 
 * 
 */
package com.javaaid.hackerrank.solutions.datastructures.linkedlists;

/**
 * @author Kanahaiya Gupta
 *
 */
public class PrintInReverse {
	class Node {
		int data;
		Node next;
	}

	void ReversePrint(Node head) {
		if (head != null) {
			ReversePrint(head.next);
			System.out.println(head.data);
		}
	}

}

/**
 * 
 * Problem Statement-
 * [Print the Elements of a Linked List](https://www.hackerrank.com/challenges/print-the-elements-of-a-linked-list)  
 * 
 */
package com.javaaid.hackerrank.solutions.datastructures.linkedlists;

/**
 * 
 * @author Kanahaiya Gupta
 *
 */
class PrintTheElementsOfALinkedList {

	class Node {
		int data;
		Node next;
	}

	void Print(Node head) {
		Node current = head;
		while (current != null) {
			System.out.println(current.data);
			current = current.next;
		}

	}
}

/**
 * 
 * Problem Statement-
 * [Compare two linked lists](https://www.hackerrank.com/challenges/compare-two-linked-lists/problem) 
 * 
 */
package com.javaaid.hackerrank.solutions.datastructures.linkedlists;

/**
 * @author Kanahaiya Gupta
 *
 */
public class CompareTwoLinkedLists {
	class Node {
		int data;
		Node next;
	}

	int CompareLists(Node headA, Node headB) {
		while (headA != null && headB != null) {
			if (headA.data != headB.data) {
				return 0;

			} else {
				headA = headA.next;
				headB = headB.next;
			}

		}

		if ((headA == null) && (headB == null)) {
			return 1;
		} else {
			return 0;

		}
	}
}

/**
 * 
 * Problem Statement-
 * [Encryption](https://www.hackerrank.com/challenges/encryption/problem)
 * 
 */
package org.javaaid.hackerrank.solutions.implementation.bruteforce;

import java.util.Scanner;

/**
 * @author Kanahaiya Gupta
 *
 */
public class Encryption {

	 static String encryption(String s) {
	        int length=s.length();
	        double rows=Math.floor(Math.sqrt(length));
	        double cols=Math.ceil(Math.sqrt(length));
	        int len=(int) (rows>cols?rows:cols);
	        String result="";
	        for(int i=0;i

/**
 * 
 */
package com.javaaid.hackerrank.solutions.languages.java.advanced;

/**
 * @author Kanahaiya Gupta
 *
 */
public class PrimeChecker {
	public void checkPrime(int... num) {
		String str = "";
		for (int n : num) {
			boolean found = true;
			if (n <= 3 && n > 1) {
				str += n + " ";
			} else {
				for (int i = 2; i <= Math.sqrt(n); i++) {
					if (n % i == 0) {
						found = false;
						break;
					}
				}
				if (found && n != 1) {
					str += n + " ";
				}
			}
		}
		System.out.println(str);
	}
}

/**
 * 
 */
package com.javaaid.hackerrank.solutions.languages.java.strings;

import java.util.Scanner;
import java.util.regex.Matcher;
import java.util.regex.Pattern;

/**
 * @author Kanahaiya Gupta
 *
 */
public class JavaRegex2DuplicateWords {
	public static void main(String[] args) {

		String regex = "\\b(\\w+)(\\b\\W+\\b\\1\\b)*";
		Pattern p = Pattern.compile(regex, Pattern.MULTILINE + Pattern.CASE_INSENSITIVE);

		Scanner in = new Scanner(System.in);
		int numSentences = Integer.parseInt(in.nextLine());

		while (numSentences-- > 0) {
			String input = in.nextLine();

			Matcher m = p.matcher(input);

			// Check for subsequences of input that match the compiled pattern
			while (m.find()) {
				input = input.replaceAll(m.group(), m.group(1));
			}

			// Prints the modified sentence.
			System.out.println(input);
		}

		in.close();
	}
}

/**
 * 
 * Problem Statement-
 * [Insertion Sort - Part 1](https://www.hackerrank.com/challenges/insertionsort1/problem)
 * 
 */
package com.javaaid.hackerrank.solutions.algorithms.sorting;

import java.util.Scanner;

/**
 * @author Kanahaiya Gupta
 *
 */
public class InsertionSortPart1 {
	public static void insertIntoSorted(int[] ar) {
		int length = ar.length;
		int elementNeedToBeInserted = ar[length - 1];
		for (int i = length - 2; i >= 0; i--) {
			if (ar[i] > elementNeedToBeInserted) {
				ar[i + 1] = ar[i];
				printArray(ar);

			} else {
				ar[i + 1] = elementNeedToBeInserted;
				printArray(ar);
				break;
			}
			if ((i == 0) && (ar[i] > elementNeedToBeInserted)) {
				ar[i] = elementNeedToBeInserted;
				printArray(ar);
			}
		}

	}

	/* Tail starts here */
	public static void main(String[] args) {
		Scanner in = new Scanner(System.in);
		int s = in.nextInt();
		int[] ar = new int[s];
		for (int i = 0; i < s; i++) {
			ar[i] = in.nextInt();
		}
		insertIntoSorted(ar);
		in.close();
	}

	private static void printArray(int[] ar) {
		for (int n : ar) {
			System.out.print(n + " ");
		}
		System.out.println("");
	}
}

/**
 * 
 * Problem Statement-
 * [Interfaces](https://www.hackerrank.com/challenges/30-interfaces/problem) 
 * 
 */
package com.javaaid.hackerrank.solutions.thirtydaysofcode;

import java.util.Scanner;

/**
 * @author Kanahaiya Gupta
 *
 */
interface AdvancedArithmetic{
	   int divisorSum(int n);
	}
//renamed Calculator class to Calculator2 class as its already present in Day17 question
class Calculator2 implements AdvancedArithmetic{
    
    public int divisorSum(int n){
        if(n==1)return 1;
       int sum=1+n,r=0;
        for(int i=2;i

/**
 * 
 * Problem Statement-
 * [DP: Coin Change](https://www.hackerrank.com/challenges/ctci-coin-change/problem)
 * 
 */
package com.javaaid.hackerrank.solutions.tutorials.ctci;

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

/**
 * @author Kanahaiya Gupta
 *
 */
public class DPCoinChange {
	public static void main(String[] args) {
		Scanner in = new Scanner(System.in);
		int n = in.nextInt();
		int m = in.nextInt();
		int coins[] = new int[m];
		for (int coins_i = 0; coins_i < m; coins_i++) {
			coins[coins_i] = in.nextInt();
		}
//	        approach1(n, coins);
//	        approach2(n, coins);
		approach3(n, coins);
//	        approach4(n, coins);
		in.close();
	}

	/**
	 * @param n
	 * @param coins
	 */
	private static void approach4(int n, int[] coins) {
		long result = noOfWaysToGetChangeUsingRecursionWithMemo2(coins, n);
		System.out.println(result);
	}

	/**
	 * @param n
	 * @param coins
	 */
	private static void approach3(int n, int[] coins) {
		long result = noOfWaysToGetChangeUsingDP(coins, n);
		System.out.println(result);
	}

	/**
	 * @param n
	 * @param coins
	 */
	private static void approach2(int n, int[] coins) {
		long memo[][] = new long[n + 1][coins.length + 1];
		memo[0][0] = 1;
		long result = noOfWaysToGetChangeUsingRecursionWithMemo(coins, n, 0, memo);
		System.out.println(result);
	}

	/**
	 * @param n
	 * @param coins
	 */
	private static void approach1(int n, int[] coins) {
		long result = noOfWaysToGetChangeUsingRecusion(coins, n, 0);
		System.out.println(result);
	}

	/**
	 * method1 with recursion
	 * 
	 * @param coins
	 * @param n
	 * @return
	 */
	private static long noOfWaysToGetChangeUsingRecusion(int[] coins, int n, int index) {
		if (n == 0)
			return 1;
		if (n < 0 || index >= coins.length)
			return 0;
		return noOfWaysToGetChangeUsingRecusion(coins, n - coins[index], index)
				+ noOfWaysToGetChangeUsingRecusion(coins, n, index + 1);
	}

	/**
	 * method2 with recursion with memorization
	 * 
	 * @param coins
	 * @param n
	 * @return
	 */
	private static long noOfWaysToGetChangeUsingRecursionWithMemo(int[] coins, int n, int index, long[][] memo) {
		if (n == 0)
			return 1;
		if (n < 0 || index >= coins.length)
			return 0;
		if (memo[n][index] != 0)
			return memo[n][index];
		return memo[n][index] = noOfWaysToGetChangeUsingRecursionWithMemo(coins, n - coins[index], index, memo)
				+ noOfWaysToGetChangeUsingRecursionWithMemo(coins, n, index + 1, memo);
	}

	/**
	 * method3 with recursion with memorizaion with hashmap(alternate of method2)
	 * 
	 * @param coins
	 * @param money
	 * @return
	 */
	private static long noOfWaysToGetChangeUsingRecursionWithMemo2(int[] coins, int n) {
		return makeChange(coins, n, 0, new HashMap());
	}

	private static long makeChange(int[] coins, int money, int index, HashMap memo) {
		if (money == 0)
			return 1;
		if (index >= coins.length)
			return 0;

		String key = money + "-" + index;
		if (memo.containsKey(key)) {
			return memo.get(key);
		}

		int amountWithCoin = 0;
		long ways = 0;
		while (amountWithCoin <= money) {
			int remaining = money - amountWithCoin;
			ways += makeChange(coins, remaining, index + 1, memo);
			amountWithCoin += coins[index];
		}
		memo.put(key, ways);
		return ways;
	}

	/**
	 * method4 using dynamic programming approach
	 * 
	 * @param coins
	 * @param n
	 * @param i
	 * @return
	 */
	private static long noOfWaysToGetChangeUsingDP(int[] coins, int n) {
		long dp[] = new long[n + 1];
		dp[0] = 1;
		for (int coin : coins) {
			for (int j = coin; j <= n; j++) {
				dp[j] += dp[j - coin];
			}
		}
		return dp[n];
	}
}