CareerCup

Please look at the question again. No Recursion.

Package different fruit is not invalid test case, I think.

Main File:
abc
abc

Secondary File:
abc

your algorithm will give true, yet it should give false!

QR-Quadtree

How about this test case: {6,7,6} k = 2
ans: {7,7}?

@eugene.yarovoi , why???
You need to give a counter example, please.

I think the question is a little bit weird...
now, consider an example with 3 numbers: a0, a1, a2
step 1:
we compare a0 and a1. result a0<a1

step 2:
we compare a1 and a2. result a1<a2 (yet we cannot guarantee it)

in this specific case, the number of comparison is 2, we have a0<a1<a2, so median is a1.

I think this is the minimum comparison number. Yet we need the number sequence satisfies some conditions.

We still use the previous example. If a1>a2. We would not know which one is median. So we need to compare a0 and a2 again.

For this case, the number of comparison would be 3. But this is worst case.


Basically, for n number , we need to do at least n-1 comparisons to find the median if data sequence satisfies some conditions.

So if we have 5 numbers, we need 4 comparison times.

Please correct me if I am wrong...

public void reverse(){
		if(head == null){
			return;
		}
		Node ptr = head;
		Node prev = null;
		while(ptr != null){
			Node tmp = ptr.next;
			ptr.next = prev;
			prev = ptr;
			ptr = tmp;
		}
		head = prev;
	}

public static int maxCirSubarray(int[] array) {
		int kadane_max = kadane(array);
		int corner_case_max = 0;
		for (int i = 0; i < array.length; i++) {
			corner_case_max += array[i];
			array[i] = -array[i];
		}
		corner_case_max += kadane(array);
		return (kadane_max > corner_case_max) ? kadane_max : corner_case_max;
	}

	public static int kadane(int[] array) {
		if (array == null || array.length == 0) {
			return 0;
		}
		int max_so_far = 0;
		int max_ending_here = 0;
		for (int i = 0; i < array.length; i++) {
			max_ending_here += array[i];
			if (max_ending_here < 0) {
				max_ending_here = 0;
			}
			if (max_ending_here > max_so_far) {
				max_so_far = max_ending_here;
			}
		}
		return max_so_far;
	}

public void postorder_recursive() {
		postorder_recursiveT(root);
	}

	private void postorder_recursiveT(TreeNode node) {
		if (node == null) {
			return;
		}
		TreeNode prev = null;
		Stack<TreeNode> stack = new Stack<TreeNode>();
		stack.push(node);
		while (!stack.isEmpty()) {
			TreeNode curr = stack.peek();
			if (prev == null || prev.left == curr || prev.right == curr) {
				if (curr.left != null) {
					// left child is not null
					stack.push(curr.left);
				} else if (curr.right != null) {
					// right child is not null
					stack.push(curr.right);
				} else {
					// leaf
					System.out.print(curr.element + " ");
					stack.pop();
				}
			} else if (prev == curr.left) {
				// traverse up from left child
				if (curr.right != null) {
					stack.push(curr.right);
				} else {
					System.out.print(curr.element + " ");
					stack.pop();
				}
			} else if (prev == curr.right) {
				// traverse up from right child
				System.out.print(curr.element + " ");
				stack.pop();
			}
			prev = curr;
		}

	}

public void inorder_recursive() {
		inorder_recursiveT(root);
		System.out.println();
	}

	private void inorder_recursiveT(TreeNode node) {
		Stack<TreeNode> stack = new Stack<TreeNode>();
		if (node == null) {
			return;
		}
		TreeNode curr = root;
		while (!stack.isEmpty() || curr != null) {
			if (curr != null) {
				stack.push(curr);
				curr = curr.left;
			} else {
				curr = stack.peek();
				stack.pop();
				System.out.print(curr.element + " ");
				curr = curr.right;
			}
		}
	}

public class ConvertToAlphabet {
	static char[] array;

	static {
		array = new char[27];
		for (int i = 1; i <= 26; i++) {
			array[i] = (char) (i + 96);
		}
	}

	public static String convert(int n) {
		if (n <= 0) {
			return "";
		}
		int remainder = n % 26;
		if (remainder == 0) {
			return "z" + convert((n - 1) / 26);
		} else {
			return array[remainder] + convert(n / 26);
		}
	}

	public static void main(String[] args) {
		System.out.println(convert(702));
	}
}

Question:
array: 1 1 0 0 0 1 1
we have three equilibrium point in this array. Which one should we return?

public static int quickSelection(int[] array, int k) {
		return quickSelectionT(array, 0, array.length - 1, k);
	}

	private static int quickSelectionT(int[] array, int left, int right, int k) {
		if (left == right) {
			return array[left];
		}
		int pivotNewIndex = partition(array, left, right, right - 1);
		int pivotDist = pivotNewIndex - left + 1;
		if (pivotDist == k) {
			return array[k];
		} else if (k < pivotDist) {
			return quickSelectionT(array, left, pivotNewIndex - 1, k);
		} else {
			return quickSelectionT(array, pivotNewIndex + 1, right, k
					- pivotDist);
		}
	}

	private static int partition(int[] array, int left, int right, int pivot) {
		int pivotValue = array[pivot];
		swap(array, pivot, right);// move it to the right place
		int index = left;
		for (int i = left; i < right - 1; i++) {
			if (array[i] < pivotValue) {
				swap(array, i, index);
				index++;
			}
		}
		swap(array, right, index);
		return index;
	}

Point:
Error conditions don't get missed using exceptions.

select (select sum(salary) from employee where salary = (select max(salary) from employee)
- select sum(salary) from employee where salary = (select min(salary) from employee)) from dual;

The basic idea here is using Newton Raphson:
y = x^2

y' = 2x

x f(x) f'(x) x' = x - f(x)/f'(x)

we use x' to replace x in each iteration until the difference value is smaller than a constant (usually 0.0000001)

At last, we will get an approximate result for x (x = sqrt(y) )

public Integer five_th() {
		if (size < 5) {
			System.out.println("The number of array is not enough!");
			return null;
		}
		Node ptr = head;
		int step = 5;
		while (step > 0) {
			ptr = ptr.next;
			step--;
		}
		Node ptr2 = head;
		while (ptr != null) {
			ptr = ptr.next;
			ptr2 = ptr2.next;
		}
		return ptr2.value;
	}

public boolean isBST() {
		if (root == null) {
			return true;
		}
		//initialize min
		TreeNode ptr = root;
		while(ptr.left != null){
			ptr = ptr.left;
		}
		Integer min = ptr.element;
		
		//initialize max
		ptr = root;
		while(ptr.right != null){
			ptr = ptr.right;
		}
		Integer max = ptr.element;
		
		return isBST_helper(root, min, max);
	}

	private boolean isBST_helper(TreeNode node, Integer min, Integer max) {
		if (node == null)
			return true;
		if (node.element > max || node.element < min) {
			return false;
		}
		return isBST_helper(node.left, min, node.element - 1)
				&& isBST_helper(node.right, node.element + 1, max);
	}

public TreeNode kthLargestNode(int k) {
		return kthLargestNodeT(root, k);
	}

	private TreeNode kthLargestNodeT(TreeNode node, int k) {
		if (node == null) {
			return null;
		}
		int L = sizeOfBSTT(node.left) + 1;
		if (L == k) {
			return node;
		}
		if (L > k) {
			return kthLargestNodeT(node.left, k);
		} else {
			return kthLargestNodeT(node.right, k - L);
		}
	}

	public int sizeOfBST() {
		return sizeOfBSTT(root);
	}

	private int sizeOfBSTT(TreeNode node) {
		if (node == null) {
			return 0;
		}
		return sizeOfBSTT(node.left) + 1 + sizeOfBSTT(node.right);
	}

public static void remove(int[] A, int[] B, LinkedList<Integer> C) {
		if (A == null || B == null || C == null) {
			return;
		}

		for (int i = 0; i < C.size(); i++) {
			boolean flag = false;
			int ptrA = 0;
			int ptrB = B.length - 1;
			while (ptrA < A.length && ptrB >= 0) {
				if (A[ptrA] + B[ptrB] == C.get(i)) {
					C.remove(i);
					flag = true;
					i--;
					break;
				} else if (A[ptrA] + B[ptrB] < C.get(i)) {
					ptrA++;
				} else {
					ptrB--;
				}
			}
			if (flag == false) {
				ptrA = A.length - 1;
				ptrB = 0;
				while (ptrB <B.length && ptrA >= 0) {
					if (A[ptrA] + B[ptrB] == C.get(i)) {
						C.remove(i);
						i--;
						break;
					} else if (A[ptrA] + B[ptrB] < C.get(i)) {
						ptrB++;
					} else {
						ptrA--;
					}
				}
			}
		}
		for(Integer i:C){
			System.out.print(i+" ");
		}
	}

No solution in this post is correct!

public void treeToDoublyLinkedList() {
		TreeNode head = null;
		TreeNode prev = null;
		treeToDoublyLinkedListT(root, head, prev);
	}

	private void treeToDoublyLinkedListT(TreeNode p, TreeNode head,
			TreeNode prev) {
		if (p == null) {
			return;
		}

		treeToDoublyLinkedListT(p.left, head, prev);
		p.left = prev;
		
		if (prev != null) {
			prev.right = p;
		} else {
			head = p;
		}

		TreeNode right = p.right;
		head.left = p;
		p.right = head;
		
		prev = p;
		treeToDoublyLinkedListT(right, head, prev);
	}

public static void removeSpace(char[] string) {
		if (string == null || string.length == 0) {
			return;
		}

		int p1 = 0;
		int p2 = 0;

		do {
			while (p2 < string.length && string[p2] == ' ') {
				p2++;
			}
			if (p2 == string.length) {
				break;
			}
			string[p1++] = string[p2++];
		} while (p1 < string.length && p2 < string.length);

		for (int p = p1; p < string.length; p++) {
			string[p] = 0;
		}

		for (char c : string) {
			System.out.print(c + " ");
		}
		
		System.out.println();
	}

DP
Base Case:
OBST(i,0) = 0 OBST(0,j) = 0

Sub Optimal Problem:
OBST(i,j) = OBST(i,r-1)+P(r)+OBST(r+1,j) + Sum(pk)(i<=k<=j)
i<=r<=j

import java.util.ArrayList;

public class GrayCode {

	public static ArrayList<Integer> grayCode(int n) {
		ArrayList<Integer> list = new ArrayList<Integer>();
		if (n == 0) {
			list.add(0);
			return list;
		} else {
			ArrayList<Integer> prev = grayCode(n - 1);
			list.addAll(prev);
			for (int i = prev.size() - 1; i >= 0; i--) {
				list.add(prev.get(i) + (int) Math.pow(2.0, n - 1));

			}
			return list;
		}

	}

	public static void main(String[] args) {
		ArrayList<Integer> result = grayCode(2);
		for (int i : result) {
			System.out.print(i + " ");
		}
		// you could generate to binary form
		for (int i : result) {
			System.out.print(Integer.toBinaryString(i) + " ");
		}
	}

}

public class ArmStrongNumber {

	public static void armStrongNumber(int n) {
		if (n < 0) {
			return;
		}
		while (n > 0) {
			int sum = 0;
			int number = n;
			while (number > 0) {
				int remainder = number % 10;
				sum = sum + remainder * remainder * remainder;
				number /= 10;
			}
			if (sum == n) {
				System.out.println(n);
			}
			n--;
		}
	}

	public static void main(String[] args) {
		armStrongNumber(999);
	}

}

Please correct me if I am wrong!

public class MagicNumber {

	public static void findMagicNumber(int[] array) {
		if (array == null || array.length == 0) {
			return;
		}
		int low = 0;
		int high = array.length - 1;
		while (low <= high) {
			if (array[low] == low) {
				System.out.println("Magic number:" + low);
			}
			if (array[high] == high) {
				System.out.println("Magic number:" + high);
			}
			low++;
			high--;
		}
	}

	public static void main(String[] args) {
		int[] array = {-10,-5,2,2,2,2,4,7,9,12,13};
		findMagicNumber(array);
	}

}

BST->LinkedList is possible by using Morris's traversing
LinkedList -> BST is not possible, I think. Because you could not locate which one is the root of this tree. So you will have multiple choices to create this tree.

private void morrisTraversalT(TreeNode root){
		if(root == null){
			return;
		}
		TreeNode current = root;
		TreeNode pre = null;
		while(current != null){
			if(current.left == null){
				System.out.print(current.element + " ");
				current = current.right;
			}else{
				//find the predecessor of current
				pre = current.left;
				while(pre.right != null && pre.right != current)
					pre = pre.right;
				//make current as right child of its inorder predecessor
				if(pre.right == null){
					pre.right = current;
					current = current.left;
				}
				else{
					//revert the changes made in if part to restore the original tree
					pre.right = null;
					System.out.print(current.element + " ");
					current = current.right;
				}
			}
		}
	}

Oh ya, you are right. The output should not include 1 1. Sorry. I have changed it. Thank you!

public class AdditionOfTwoList {

	public static void add(LinkedList<Integer> l1, LinkedList<Integer> l2) {
		if (l1 == null || l1.size() == 0 || l2 == null || l2.size() == 0) {
			return;
		}
		int s1 = l1.size();
		int s2 = l2.size();

		LinkedList<Integer> result = new LinkedList<Integer>();
		int carryIn = 0;
		int s = s1 < s2 ? s1 : s2;
		for (int i = 0; i < s; i++) {
			int a = l1.get(i);
			int b = l2.get(i);
			int c = a + b + carryIn;
			carryIn = 0;
			if (c > 9) {
				c = c - 10;
				carryIn = 1;
			}
			result.add(c);
		}
		if (s1 < s2) {
			for (int i = s1; i < s2; i++) {
				int c = l2.get(i) + carryIn;
				carryIn = 0;
				result.add(c);
			}
		} else if (s1 > s2) {
			for (int i = s2; i < s1; i++) {
				int c = l1.get(i) + carryIn;
				carryIn = 0;
				result.add(c);
			}
		} else {
			if (carryIn == 1) {
				result.add(1);
			}
		}
		for (Integer i : result) {
			System.out.print(i + " ");
		}
	}

	public static void main(String[] args) {
		LinkedList<Integer> l1 = new LinkedList<Integer>();
		LinkedList<Integer> l2 = new LinkedList<Integer>();
		l1.add(5);
		l1.add(6);
		l1.add(3);
		
		l2.add(8);
		l2.add(4);
		l2.add(2);
		add(l1,l2);
	}
}

Also, what about aa27 ? Is it possible?

I just have a question. What about z26? So in this case, there is 2 numbers at the end of it...

@Arulmozhi
I think you are right. Why lots of people try to work around it?

public class PairIndexSum {
	public static void printIndexPair(int[] array, int sum) {
		Map<Integer, LinkedList<Integer>> map = new HashMap<Integer, LinkedList<Integer>>();
		for (int i = 0; i < array.length; i++) {
			if (map.containsKey(array[i])) {
				map.get(array[i]).add(i);
			} else {
				LinkedList<Integer> list = new LinkedList<Integer>();
				list.add(i);
				map.put(array[i], list);
			}
		}
		for (int i = 0; i < array.length; i++) {
			if (map.containsKey(sum - array[i])) {
				LinkedList<Integer> list = map.get(sum - array[i]);
				for (Integer n : list) {
					if(i != n){
						System.out.println("Index:" + i + " " + n);
					}
				}
				map.remove(array[i]);
				map.remove(sum - array[i]);
			}
		}
	}

	public static void main(String[] args) {
		int[] array = { 1, 4, 4, 3, 7, 5, 8 };
		printIndexPair(array, 8);
	}

}

public class ExcelSheet {
	static char[] array;
	static {
		array = new char[26];
		for (int i = 0; i < 26; i++) {
			array[i] = (char) (i + 97);
		}
	}
	public static void convert(int n){
		System.out.println(convertInteger(n));
	}
	public static String convertInteger(int n) {
		if (n <= 0) {
			return "a";
		}
		if(n < 26){
			return ""+array[n];
		}
		int remainder = n % 26;
		if (remainder == 0) {
			return convertInteger((n - 1) / 26) + array[remainder];
		} else {
			return convertInteger(n / 26 - 1) + array[remainder];
		}
	}

	public static void main(String[] args) {
		convert(76);
	}

}

public static int NO_NODES_FOUND = 0;
	public static int ONE_NODES_FOUND = 1;
	public static int TWO_NODES_FOUND = 2;
	
	public int covers(TreeNode root,TreeNode p, TreeNode q){
		int ret = NO_NODES_FOUND;
		if(root == null){
			return ret;
		}
		if(root == p || root == q){
			ret += 1;
		}
		ret += covers(root.left,p,q);
		if(ret == TWO_NODES_FOUND){
			return ret;
		}
		return ret+=covers(root.right,p,q);
	}
	
	public TreeNode commonAncestor(TreeNode root, TreeNode p, TreeNode q){
		if( p == q && (root.left == q || root.right == p)){
			return root;
		}
		int nodesFromLeft = covers(root.left,p,q);
		if(nodesFromLeft == TWO_NODES_FOUND){
			if(root.left == p || root.left == q){
				return root;
			}else{
				return commonAncestor(root.left,p,q);
			}
		}else if(nodesFromLeft == ONE_NODES_FOUND){
			if(root == p){
				return p;
			}else if(root == q){
				return q;
			}
		}
		int nodesFromRight = covers(root.right,p,q);
		if(nodesFromRight == TWO_NODES_FOUND){
			if(root.right == p || root.right == q){
				return root;
			}else{
				return commonAncestor(root.right,p,q);
			}
		}else if(nodesFromRight == ONE_NODES_FOUND){
			if(root == p){
				return p;
			}else if(root == q){
				return q;
			}
		}
		if(nodesFromLeft == ONE_NODES_FOUND && nodesFromRight == ONE_NODES_FOUND){
			return root;
		}else{
			return null;
		}
	}

@vik
OMG, this is so complicated. Could you explain more about it? Thank you.

@optimumsPrime
Your solution is still O(n^2)

Your method is wrong.
First, you cannot assume there is a color field in Binary Search TreeNode.
Second, your algo will always go left bottom until leaf...

Actually,
if we use hashmap, O(n) space complexity and O(n) time complexity
if we use loop, O(1) space complexity and O(n^2) time complexity.

Step1:
define interface List<T> which includes necessary method declaration.

Step2:
define class LinkedList<T> which implements List<T>, Serialiazable

public class DutchNantionalFlag {
	// in array, only 0,1,2 includes
	public static void DutchNationalSort(int[] array) {
		int count0 = 0;
		int count1 = 0;
		int count2 = 0;
		for (int i = 0; i < array.length; i++) {
			if (array[i] == 0)
				count0++;
			if (array[i] == 1)
				count1++;
			if (array[i] == 2)
				count2++;
		}
		for (int i = 0; i < count0; i++) {
			array[i] = 0;
		}
		for (int i = count0; i < count0 + count1; i++) {
			array[i] = 1;
		}
		for (int i = count0 + count1; i < count0 + count1 + count2; i++) {
			array[i] = 2;
		}
		for (int i : array) {
			System.out.print(i);
		}
	}

	public static void dutchFlagSort(int[] arr, int p, int k) {
		int head = 0;
		int tail = arr.length - 1;
		for (int i = 0; i <= tail;) {
			if (arr[i] < p) {
				swap(arr, i, head);
				head++;
				i++;
			} else if (arr[i] >= k) {
				swap(arr, i, tail);
				tail--;
			} else {
				i++;
			}
		}
		for (int i : arr) {
			System.out.print(i);
		}
	}

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

	public static void main(String[] args) {
		int[] array = { 1, 2, 1, 2, 0, 1, 2, 0, 0, 2, 1, 0 };
		DutchNationalSort(array);
		dutchFlagSort(array,1,2);
	}

}

@Lalitha, you are right. The time complexity is O(n^2).
But I think it's necessary because we need to check Consecutive Letter.
Do you have some better idea?

public void find(int nth) {
		if (nth >= M * N) {
			return;
		}
		int[] rows = new int[M];
		for (int i = 0; i < M; i++) {
			rows[i] = 0;
		}
		int ptr = 0;
		int min = Integer.MAX_VALUE;
		for (int i = 0; i < nth; i++) {
			min = Integer.MAX_VALUE;
			int r = 0;
			for (int k = 0; k <= ptr; k++) {
				if (matrix[k][rows[k]] < min) {
					min = matrix[k][rows[k]];
					r =k;
				}
			}
			if(rows[r] == 0){
				ptr++;
				if(ptr == M){
					ptr--;
				}
			}
			rows[r]++;
		}
		System.out.println(min);
	}

import java.util.ArrayDeque;
import java.util.Deque;
import java.util.Iterator;
import java.util.LinkedList;
import java.util.Queue;

public class BSTPrint {
	TreeNode root;

	class TreeNode {
		double value;
		TreeNode left;
		TreeNode right;

		public TreeNode(double value) {
			super();
			this.value = value;
			left = null;
			right = null;
		};

	}

	public void insert(double value) {
		root = insertT(root, value);
	}

	public TreeNode insertT(TreeNode root, double value) {
		if (root == null) {
			TreeNode r = new TreeNode(value);
			return r;
		}
		if (value > root.value) {
			// right
			root.right = insertT(root.right, value);
		} else if (value < root.value) {
			root.left = insertT(root.left, value);
		}
		return root;
	}

	public void inorder() {
		inorderT(root);
		System.out.println();
	}

	private void inorderT(TreeNode root) {
		if (root == null) {
			return;
		}
		inorderT(root.left);
		System.out.print(root.value + "\t");
		inorderT(root.right);
	}

	/**
	 * WAP to print the node values of a binary tree - Even level starting from
	 * right to left - Odd level starting from left to right Assume that level
	 * of root is 1.
	 */
	public void levelPrint() {
		if (root == null) {
			return;
		}
		Deque<TreeNode> deque = new ArrayDeque<TreeNode>();
		deque.offerLast(root);
		int level = 1;
		while (!deque.isEmpty()) {
			if (level % 2 == 1) {
				for (Iterator<TreeNode> iterator = deque.iterator(); iterator
						.hasNext();) {
					System.out.print(iterator.next().value + " ");
				}
			} else {
				for (Iterator<TreeNode> iterator = deque.descendingIterator(); iterator
						.hasNext();) {
					System.out.print(iterator.next().value + " ");
				}
			}
			int size = deque.size();
			while (size > 0) {
				TreeNode node = deque.pollFirst();
				if (node.left != null)
					deque.addLast(node.left);
				if (node.right != null)
					deque.addLast(node.right);
				size--;
			}
			level++;
		}
	}

	public static void main(String[] args) {
		BSTPrint bst = new BSTPrint();
		bst.insert(6);
		bst.insert(5);
		bst.insert(4);
		bst.insert(2);
		bst.insert(8);
		bst.insert(7);
		bst.insert(3);
		bst.insert(9);
		bst.levelPrint();
	}

}

public class MajorityElement {
	
	//Moore's Voting Algorithm
	public static Integer majorityEle(int[] array) {
		if (array == null && array.length == 0) {
			return null;
		}
		int candidate = 0;
		int count = 1;
		for (int i = 1; i < array.length; i++) {
			if (array[i] == array[i - 1]) {
				count++;
			} else {
				count--;
			}
			if (count == 0) {
				candidate = i;
			}
		}
		count = 0;
		for (int i = 0; i < array.length; i++) {
			if (array[i] == array[candidate]) {
				count++;
			}
		}
		if (count > array.length / 2) {
			return array[candidate];
		}
		return null;
	}

	public static void main(String[] args) {
//		int[] array = {3,3,4,4,5,3,3,4};
		int[] array = {2,4,2,5,2,2,6,6,6};
		System.out.println(majorityEle(array));
	}

}

import java.util.Calendar;
import java.util.GregorianCalendar;

public class ParseDate {

	/**
	 * Given today is Thursday and 23rd August, 2012. Write a function to input
	 * a date (future or past) and tell which day it is:- int day_of_week(int
	 * dd, int mm, int yyyy) Mon -1, Tue - 2, Wed -3......Sun-7
	 */

	public static int day_of_week(int dd, int mm, int yyyy) {
		Calendar cal = new GregorianCalendar();
		cal.set(yyyy, mm, dd);
		
		Calendar today = new GregorianCalendar();
		today.set(2012, 7, 23);
		
		int diff = 4;
		if (today.compareTo(cal) < 0) {
			while (today.compareTo(cal) != 0) {
				today.add(Calendar.DAY_OF_YEAR, 1);
				diff = (diff + 1) % 7;
				if (diff == 0) {
					diff = 7;
				}
			}
		} else if (today.compareTo(cal) > 0) {
			while (today.compareTo(cal) != 0) {
				today.add(Calendar.DAY_OF_YEAR, -1);
				diff = (diff - 1) % 7;
				if (diff == 0) {
					diff = 7;
				}
			}
		} else {
			;
		}
		System.out.println(diff);
		return 0;
	}

	public static void main(String[] args) {
		day_of_week(1, 6, 2012);
	}

}

public class DecodeInteger {

	public static char[] array;

	static {
		array = new char[27];
		array[0] = 0;
		for (int i = 1; i < 27; i++) {
			array[i] = (char) (i + 96);
		}
	}

	public static void decodeInt(int num) {
		int remainder;
		if (num <= 26) {
			System.out.print(array[num]);
		} else {
			remainder = num % 26;
			if (remainder == 0) {
				decodeInt(num / 26 - 1);
				System.out.print("z");
			} else {
				decodeInt(num / 26);
				System.out.print(array[remainder]);
			}
		}
	}

	public static void main(String[] args) {
		decodeInt(26);
	}

}

public class SwapBit {
	//num is unsigned, 32 bit
	public static int swapBit(int num){
		int odds = (0xAAAAAAAA & num) >> 1;
		int evens = (0x55555555 & num) << 1;
		return odds | evens;
	}
	/**
	 * @param args
	 */
	public static void main(String[] args) {
		System.out.println(swapBit(5));
	}

}