Saturday, November 15, 2014

Given a number, find the next smallest palindrome

Reference
http://www.geeksforgeeks.org/given-a-number-find-next-smallest-palindrome-larger-than-this-number/

Problem statement
Given a number, find the next smallest palindrome larger than this number. 
For example, 
if the input number is “2 3 5 4 5″, the output should be “2 3 6 3 2″. 
if the input number is “9 9 9″, the output should be “1 0 0 1″.
if the input number is “1 9 1″, the output should be “2 0 2″.

My approach.


Please find below recursive approach for find the next smallest palindrome"

Algorithm :- 
If number is all 9's say 99 then then its palindrome will be 101. For 999 answer is 1001 and so on

For other cases 
if input is 1356 then we will start with first & digit same as input 1 _ _ 1
Now we will call same function to get palindrome of internal number by striping first and last digit viz. 35. 
So function call for 35 will return 44
So answer for 1356 is 1 4 4 1

Now if number is 1996 the we will start with 1 _ _ 1
Now we will call same function to get palindrome of internal number by striping first and last digit viz. 99. 
So function call for 99 will return 101
So it returned palindrome of length more than 2; it means we should increase outer digit to make it 2 _ _ 2
And we should fill it up with zeros.
Thus answer for 1996 is 2002

Code is shared at 
http://ideone.com/3sGpMr

Java code
package stringsequennce;

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

public class NextBiggerPalindromeNumber {

/**
Given a number, find the next smallest palindrome
Given a number, find the next smallest palindrome larger than this number. For example, if the input number is “2 3 5 4 5″, the output should be “2 3 6 3 2″. And if the input number is “9 9 9″, the output should be “1 0 0 1″.

The input is assumed to be an array. Every entry in array represents a digit in input number. Let the array be ‘num[]’ and size of array be ‘n’

There can be three different types of inputs that need to be handled separately.
1) The input number is palindrome and has all 9s. For example “9 9 9″. Output should be “1 0 0 1″
2) The input number is not palindrome. For example “1 2 3 4″. Output should be “1 3 3 1″
3) The input number is palindrome and doesn’t have all 9s. For example “1 2 2 1″. Output should be “1 3 3 1″.
*/
public static void main(String[] args) {
// for(int i=1;i<10;i++){
// System.out.println("i= "+i+" "+getMaxPalindromeOfLenthN(i));
// }
int num=0;

num=999 ;
System.out.println("num= "+num +" palindrome ="+ getNextHigherPalnidromeNumber(num));

num=1234;
System.out.println("num= "+num +" palindrome ="+ getNextHigherPalnidromeNumber(num));

num=191;
System.out.println("num= "+num +" palindrome ="+ getNextHigherPalnidromeNumber(num));

}
public static int getNextHigherPalnidromeNumber(int input){
// Handle single digit numbers
if(input==9) return 11;     // For 9 next palindrome is 11

if(input<9) return input+1; // for 0 to 8 next palindrome is next number

// So now number is two digits or more
// Separate out digits 
int temp = input;
ArrayList<Integer> digitList = new ArrayList<Integer>();
while(temp>0){
digitList.add(temp%10);
temp = temp /10;
}
// digitList(0) is digit at unit place
// digitList(n) will be digit at highest place.

// Now check if input is equal to max palindrome of that length
// In that case next palindrome is min palindrome of lenght+1
if(input==getMaxPalindromeOfLenthN(digitList.size())) 
return getMinPalindromeOfLenthN(digitList.size()+1);

// It is not max palindrome of that length. next palindrome is of same length as input.
/* if input is 1356 then we will start with first & digit same as input 1 _ _ 1
*  Now we will call same function to get palindrome of internal number by striping first and last digit viz. 35. So function will return 44
*  So answer is 1 4 4 1
*  
*  Now if number is 1996 the we will start with 1 _ _ 1
*  Now we will call same function to get palindrome of internal number by striping first and last digit viz. 99. So function will return 101
*  So it returned palindrome of length more than 2; it means we should increase outer digit
*  2 _ _ 2
*  And we should fill it up with zeros so answer for 1996 is 2002
*  
*/

// Strip first and last digit
//  for number 7986  List is -> 6,8,9,7
// So starting with digit at index n-2 till index 1; prepare number
int outerdigit   =digitList.get(digitList.size()-1);
// So 7 _ _ 7   is time being 7007.
int returnVal = outerdigit*(int)Math.pow(10,digitList.size()-1) + outerdigit;

temp = 0;
for(int i=digitList.size()-2;i>=1;i--){
temp = temp*10 + digitList.get(i);
}
int palindromeForInnerNumber= getNextHigherPalnidromeNumber(temp);

// for inner number 99 palindrome will be 101. In this case we should increase higher number and use all zeros
// Inner number is of length digitList.size()-2. So palindrome of biggger length id digitList.size()-2+1
// For input number 79998 inner number is 999. And its palindrome is 1001. 
// Now outer number was decided as 7 and we had prepared temporary palindrome as 7_ _7. So we should make it 8_ _ 8 means 8008
if(palindromeForInnerNumber==getMinPalindromeOfLenthN(digitList.size()-2+1)){  
outerdigit++;
returnVal = outerdigit*(int)Math.pow(10,digitList.size()-1)+ outerdigit;
}else{
//  For input 7865 palindrome is decided as 7_ _7 i.e. 7007. Inner number is 86. Its palindrome is 99.
// Now 99 is to be fit into middle slot. So we will multiply it by 10 and add into number
// 7007 + 99*10 = 7007 + 990= 7997
returnVal= returnVal+ palindromeForInnerNumber*10 ;
}
return returnVal;
}

public static int getMinPalindromeOfLenthN(int n){
/* For length min palindromes are as follows
* 1 1
*   2 11
*   3 101
*   4 1001
*   5 10001
*/
// So 1 is present at  10^(n-1) and unit digit
// so number is 10^(n-1) + 1
if(n==1) 
return 1;

return (int)Math.pow(10, n-1) + 1;
}

public static int getMaxPalindromeOfLenthN(int n){
/* For legth max palindromes are as follows
* 1 9
*   2 99
*   3 999
*   4 9999
*/
int num =0;
for(int i=1;i<=n;i++){
num = num*10+9;
}
return num;
}


}



Sunday, November 2, 2014

Lowest Common Ancestor (LCA) in a Binary Tree

Reference :- 
http://www.geeksforgeeks.org/lowest-common-ancestor-binary-tree-set-1/

My approach :-
Method using single traversal & flags(v1 and v2) given in article can be improved further.
There we call find(lca, n2) & find(lca, n1). 
So you are traversing tree twice for looking up two keys.
What if n1 is somewhere down n2 ? All the traversal to reach till n1 is done again. 
Instead you should traverse tree just once and keep track of values found. If you find one key still continue searching further for other key. So all the traversal till this point is not needed again. 
Once you find both keys stop search.

So you maintain two flags to indicate of values are found. Initially both flags are false.
If root is equal to one value then corresponding flag is set.
Then we search sub-trees to in same way. 
After traversal is complete; if if both flag were false before this node checking and both flag are true after this node checking then this node it LCA


Java implementation 
Code is also shared at
http://ideone.com/McU0wN

package tree;

public class TreeNode {
int numKey;
char charKey;
public TreeNode left, right;


TreeNode(int keyVal){
numKey=keyVal;
}

TreeNode(char keyVal){
charKey=keyVal;
}

TreeNode(char keyVal,TreeNode leftChild, TreeNode rightChild){
charKey=keyVal;
left=leftChild;
right=rightChild;
}

public static TreeNode findLCA(TreeNode root, int val1, int val2){
LCA lcaObj = new LCA();
lcaObj.val1=val1;
lcaObj.val2=val2;
return findLCA_internal(root,lcaObj);

}

private static TreeNode findLCA_internal(TreeNode root,LCA lcaObj ){
if(root==null) return null;

if(lcaObj.val1Found && lcaObj.val2Found){
// both values are found at previous level so do nothing more
return null;
}else{
boolean val1FlagBefore = lcaObj.val1Found;
boolean val2FlagBefore = lcaObj.val2Found;

if(!lcaObj.val1Found && root.numKey==lcaObj.val1){
lcaObj.val1Found=true;
}if(!lcaObj.val2Found && root.numKey==lcaObj.val2){
lcaObj.val2Found=true;
}
TreeNode lcaPresentInLeftTree = findLCA_internal(root.left,lcaObj);
if(lcaPresentInLeftTree !=null){
return lcaPresentInLeftTree;
}else{
TreeNode lcaPresentInRightTree  = findLCA_internal(root.right,lcaObj);
if(lcaPresentInRightTree!=null) {
return lcaPresentInRightTree;
}else{
// LCA is not presnt in left tree nor it is present in right tree. So check if this node itself if LCA
//  before this node was checked ;val1 flag was false and afterwards it is true.
// ALSO
// before this node was checked; val2 flag was false and and afterwards it is true.
// This root is the LCA
if(!val1FlagBefore && lcaObj.val1Found && !val2FlagBefore && lcaObj.val2Found){
return root;
}else{
// So either or both of keys are not present in this tree
return null;
}

}
}

}
}

public static void main(String[] args) {
/*
10
/ \
   20  30
   / \
  40 50
  */
TreeNode root = new TreeNode(10);
root.left= new TreeNode(20);
root.left.left= new TreeNode(40);
root.left.right= new TreeNode(50);
root.right= new TreeNode(30);

TreeNode lcaNode = null;
lcaNode = findLCA(root, 50, 40);
System.out.println("findLCA(root, 50, 40)" + lcaNode.numKey );
lcaNode = findLCA(root, 30, 40);
System.out.println("findLCA(root, 30, 40)"+ lcaNode.numKey );
lcaNode = findLCA(root, 30, 20);
System.out.println("findLCA(root, 30, 20)"+ lcaNode.numKey );
lcaNode = findLCA(root, 50, 20);
System.out.println("findLCA(root, 50, 20)"+ lcaNode.numKey );

}

}


class LCA{
int val1,val2;
boolean val1Found=false;
boolean val2Found=false;

}


Output
findLCA(root, 50, 40)20
findLCA(root, 30, 40)10
findLCA(root, 30, 20)10
findLCA(root, 50, 20)20