Binary To Gray's Code and vice versa.

Write a recursive function to convert Binary Code of a number into its equivalent Gray's code and the other way round.


Dec  Gray   Binary
 0   000    000
 1   001    001
 2   011    010
 3   010    011
 4   110    100
 5   111    101
 6   101    110
 7   100    111

int binaryToGray(unsigned int num) {
        return (num>>1) ^ num;
}


code input/output:
Binary => Gray
000 => 000
001 => 001
010 => 011
011 => 010
100 => 110
101 => 111
110 => 101
111 => 100


Gray => Binary
000 => 000
001 => 001
011 => 010
010 => 011
110 => 100
111 => 101
101 => 110
100 => 111

Count smaller elements on right side in a given Array.

eg : [4,12,5,6,1,34,3,2]
o/p  [3,5, 3,3,0, 2,1,0]


ex2: {8, 3, 10, 1, 6, 14, 4, 7, 13}
o/p: {5, 1, 4,  0, 1, 3,  0, 0, 0}


Approach:
Example array: A: [4,12,5,6,1,34,3,2]
1. Start creating BST from the end of the array.


tree node is like:
class Node {
Integer data;
Integer left_count;
Integer counter;
Node left;
Node right;

public Node(Integer data) {
this.data = data;
this.left_count = 1;
this.counter = 0;
this.left = null; this.right = null;
}
}


2. every tree node has left_count (size of left subtree + 1) and counter (number of smaller elements on the right side.)


3. Recursion looks like this:
public static Node insertIntoBST(Node node, int value, int leftSum) {
if (null == node) { return new Node(value); }
if (value <= node.data) {
++node.left_count;
node.left = insertIntoBST(node.left, value,leftSum);
if (node.left.left == null && node.left.right == null)
node.left.counter = leftSum;
} else {
node.right = insertIntoBST(node.right, value, node.left_count+leftSum);
if (node.right.right == null && node.right.left == null)
node.right.counter = node.left_count+node.counter;
}
return node;
}

4. Lets trace the above code with example:
A: [4,12,5,6,1,34,3,2]


start inserting from the end of the array A.
So ..
step1: insert (2) - its the root node.
       2 (1,0) -> 1 is left_count and 0 is counter.
  

step2: insert (3) - it will go to right of 2
  2 (1,0)
   3(1,1)


step3: insert (34) - it will go to right of 3
2 (1,0)
     3(1,1)
        34(1,2)
step4: insert (1) - it will go to the left of 2.
2(2,0)
1(1,0) 3(1,1)
                  `34(1,2)


step5: insert (6) - it will go to the left of 34.
2(2,0)
1(1,0) 3(1,1)
                  34(1,2)
        6(1,3)

step6: insert (5) - it will go to the left of 6.
2(2,0)
1(1,0) 3(1,1)
          34(1,2)
    6(2,3)
5(1,3)

step7: insert (12) - it will go to the right of 12.
2(2,0)
1(1,0) 3(1,1)
34(1,2)
6(2,3)
5(1,3) 12(1,5)

step8: insert (4) - it will go to the left of 5.
2(2,0)
1(1,0) 3(1,1)
                34(1,2)
       6(3,3)
         5(2,3) 12(1,5)
     4(1,3)

4 has counter 3 because from root we take right so leftsum is now 2, again we take right from 3, so leftsum+=1 = 3, and from 34 we keep left till we insert it has left child of 5.
We are done!


Code input/ouput:
eg : [4,12,5,6,1,34,3,2]
o/p  [3,5, 3,3,0, 2,1,0]
Printing data and count of smaller elements to the right: 
1::0
2::0
3::1
4::3
5::3
6::3
12::5
34::2


ex2: {8, 3, 10, 1, 6, 14, 4, 7, 13}
o/p: {5, 1, 4,  0, 1, 3,  0, 0, 0}
Printing data and count of smaller elements to the right: 
1::0
3::1
4::0
6::1
7::0
8::5
10::4
13::0
14::3

Time complexity: O(nlogn)

Binary Tree to Doubly Linked List.

Write code to convert a binary tree to doubly link list in place.


Code input/output:


Inserting following values in BST: 
98 84 92 58 57 20 34 
Printing BST inorder: 
20 34 57 58 84 92 98 
Printing the doubly linked list: 
20 <-> 34 <-> 57 <-> 58 <-> 84 <-> 92 <-> 98 <->  points to head 

Powering a Number in O(logn) Time.

Problem:Compute a^n, where n is a natural number.
Naive algorithm:Θ(n).
a^n = a^(n/2) * a^(n/2) if n is even;
= a^((n–1)/2) * a^((n–1)/2) * a if n is odd;


Divide-and-conquer algorithm:
T(n) = T(n/2) + Θ(1) ⇒T(n) = Θ(lgn).


Input:
15
7
Output:
15^7 = 170859375


Code: