dilip.rangarajan
BAN USERthis tree is then no longer a BST.. Should that be done as well ?
- dilip.rangarajan May 06, 2012there is a cheeky way of solving this. Keep Count of all Prime numbers. the 100th number will be 1xx - xx where xx is the number of primes .... But figuring out whether is a number is prime or not is NP complete.. Just saying!!
- dilip.rangarajan May 05, 2012Do In Order traversal of the tree in O(n) time --> Sorted Order . Now it is pretty easy to find all the numbers that sum up to a given number. traverse from both ends of the in-order list. if less than sum, increment left pointer, else decrement right pointer, if equal, print numbers at left and right pointer.
- dilip.rangarajan April 22, 2012A recursive Solution is presented below.
Taking the same example as above = (god).
god..
# of characters lesser in rank than the first character (g) is 1 (= d)
# of permutations = getCountBefore(g) * (n-1)*(n-2) + getRank(remainder)
remainder in this case is od.
Rank of od is 2 (do , od) .. this is also computed using the same recursive method. we do this until we hit the base case of input string length = 1 at which point we return 1.
So for god, the trace will be
getCountBefore(g in god) * (n-1) * (n-2) [ 1 * (3-1) * (3-2) ] + getRank (od)
for od --> getCountBefore(o in od ) * (n-1) = [ 1 * 1] + getRank (d)
for d (base case) getRank(d) will return 1;
So rank of god will be 2 + 1 + 1 = 4
the java code is presented below
public int getRank(String input) {
int count = getCountBefore(input);
return getRank(input,count);
}
private int getRank(String input, int count) {
if (input == null || input.isEmpty()) return 0;
if (input.length() == 1) return 1;
else {
int n = input.length();
String remainder = input.substring(1);
if (n > 2) {
return getCountBefore(input)*(n-1)*(n-2) + getRank(remainder,getCountBefore(remainder));
}
else {
return getCountBefore(input) * (n-1) + getRank(remainder, getCountBefore(remainder));
}
}
}
private int getCountBefore(String input) {
if (input == null || input.isEmpty() || input.length() == 1) return 0;
int count = 0;
char c = input.charAt(0);
char[] charArray = input.toCharArray();
for (int i = 1; i < charArray.length; i++) {
if(charArray[i] < c) {
count++;
}
}
return count;
}
Two cases
odd size and even size.
odd size --> center is a single letter e.g. size = 5 , palindrome = madam .. center = d
even size --> center is a double letter e.g. size = 6, palindrome = maddam.. center = dd
(Counter Examples welcome)
So if odd, add the first letter in the char set once and expand around the center.
e.g. Input Set (a,b) , size = 3 . Start with a --> aaa --> bab
Then b --> aba --> bbb
Similarly, for even sized Palindrome
e.g. Input Set (a,b) size = 4, Start with aa instead of a.
aa --> aaaa --> baab
come back to next char i.e. b .. start with bb --> abba --> bbbb
here is the java code for this implementation
public static ArrayList<String> sizeKPalindromes(ArrayList<Character> charSet, int size) {
Boolean odd = false;
if ( (size & 1) > 0 ) {/* odd */
odd = true;
}
return sizeKPalindromes("", charSet, size,odd);
}
private static ArrayList<String> sizeKPalindromes(String string, ArrayList<Character> charSet, int size, Boolean odd) {
if (string == null) {
return null;
}
if (string.length() == size) {
ArrayList<String> currPalindrome = new ArrayList<String>();
currPalindrome.add(string);
return currPalindrome;
}
ArrayList<String> allPalindromeStrings = new ArrayList<String>();
for (int i = 0; i < charSet.size(); i++) {
String tempString = new String();
if (odd && string.isEmpty()) {
tempString = string + charSet.get(i);
}
else {
tempString = charSet.get(i) + string + charSet.get(i);
}
ArrayList<String> tempPalindromes = sizeKPalindromes(tempString, charSet, size, odd);
allPalindromeStrings.addAll(tempPalindromes);
}
return allPalindromeStrings;
}
Essentially the idea is the same as what candis said. Here is the code for same which I implemented in Java.
I Since the inorder is contiguous, the trick here is to find the start and end elements in the Pre-Order which are to the left of the current root node in the in-order sequence and pass it recursively to construct left and right subtrees
public void reconstructInOrderPreOrder(ArrayList<Integer> inOrder, ArrayList<Integer> preOrder) throws ConstraintViolationException {
if (inOrder.isEmpty() || preOrder.isEmpty()) {
throw new ConstraintViolationException("Invalid Input Arrays");
}
root = reconstructInOrderPreOrder(root, inOrder, preOrder);
}
public int findIndexInOrder(List<Integer> inOrder, Integer key) {
return inOrder.indexOf(key);
}
private TreeNode reconstructInOrderPreOrder(TreeNode t, List<Integer> inOrder, ArrayList<Integer> preOrder) {
if (inOrder.isEmpty() || preOrder.isEmpty()) return null;
Integer currElement = preOrder.get(0);
preOrder.remove(currElement);
Integer index = findIndexInOrder(inOrder, currElement);
t = new TreeNode(currElement);
t.left = reconstructInOrderPreOrder(t.left, inOrder.subList(0, index), preOrderSubList(preOrder, inOrder.subList(0, index)));
t.right = reconstructInOrderPreOrder(t.right, inOrder.subList(index+1, inOrder.size()), preOrderSubList(preOrder,inOrder.subList(index+1,inOrder.size())));
return t;
}
public ArrayList<Integer> preOrderSubList(List<Integer> preOrder,List<Integer> inOrderSubList) {
if (preOrder.isEmpty() || inOrderSubList.isEmpty()) {
return new ArrayList<Integer>();
}
/*if (inOrderSubList.size() == 0) {
return new ArrayList<Integer>();
}*/
int min=preOrder.indexOf(inOrderSubList.get(0)),max = 0;
for (int i = 0; i < inOrderSubList.size(); i++) {
int indexCurrElement = preOrder.indexOf(inOrderSubList.get(i));
if (indexCurrElement <= min ) min = indexCurrElement;
if (indexCurrElement >= max ) max = indexCurrElement;
}
System.out.println("min = " + min + "\tmax = " + max);
return new ArrayList<Integer>(preOrder.subList(min, max+1));
}
U just need to pass the value of prev.. Even the other solution checks all the nodes. Both are same in space and time complexity. Just different techniques.
- dilip.rangarajan May 06, 2012