Friday, September 19, 2014

Forming the nth binary sequence

A binary sequence contains 0 and 1 only
 

S.No  Binary sequence
--------------------
1     0
2     1
3     00
4     01
5     10
...

Given a number k, we have to design an algorithm to print kth binary sequence.

Initial approach (not efficient):

 
Starting from the sequence 0, this algorithm iterates k times. 


To get the next sequence, in each iteration we do the following.
 check the last index of 0 in the number

  • If it is found change that to 1 and all the digits after that to 0
  • If it is not found, the next sequence contains all 0 which is one  digit longer than previous
Efficient approach:

Observe the following. we can have
'2' single digit numbers
'4' two digit numbers
'8' three digit numbers
...
'2^i' i digit numbers


We can find the number of digits in
kth sequence by calculating the power of 2 which is less than k .

For example if
k is 5, the smallest power (s) of 2 less thank k is 4. So kth sequence has 2 digits.

To form the the sequence we need to find the binary representation of 

k - ( 2^1 + 2^2 + ...+2^s)
 

This SPOJ problem is based on the above algorithm.
 

Here is the C++ program which implements this.

Wednesday, September 17, 2014

Building a binary tree using inorder and post/pre order traversals

Given the in-order, and pre-order or post-order sequences of a binary tree, how do we construct a binary tree from them?

Given only pre-order and post order traversals, we can not construct a unique binary tree from them.

For example given 
In-order : {1, 2, 3, 4, 5, 6, 7, 8}
Pre-order: {5, 3, 2, 1, 4, 8, 6, 7}

We have to create the following binary tree
We use recursive approach for constructing a binary tree from In-order and Post-order or Pre-order traversals .

Constructing from Inorder and Preorder:

In Pre order, we first traverse the root, then left sub tree and right sub tree. So the first element in the pre order is always the root. We search for this element in the in-order sequence. This index divides the in-order sequence into left subtree and right subtree.

For example consider the following binary tree
                
                       1
               /   \
              2     3
             / \   / \   
            4   5 6   7

Inorder:  {4, 2, 5, 1, 6, 3, 7}
Preorder: {1, 2, 4, 5, 3, 6, 7}

Create 1 as the root node, 
  • all the left elements to the left of it {4, 2, 5} form the left subtree
  • all the elements to the right of it {6, 3, 7} form the right subtree

We can use the index of 1 in Inorder (in this case 3) to calculate the size of the left and right subtrees.

Size(left subtree) = index
Size(right subtree) = size-index-1

We can also use this index to calculate the offset of Inorder and Post order sequences for the subtree.

To create the left subtree we pass Inorder:{4, 2, 5} Preorder:{2, 4, 5} as parameters to the recursive call.

To create the right subtree we pass Inorder:{6, 3, 7} Preorder:{3, 6, 7} as parameters.

Constructing from Inorder and Postorder:

In post order, we first traverse the left subtree, right subtree and visit the root. So the last element in the post order sequence is the root.
Similar to the above algorithm, this element divides the in-order sequence into left subtree and right subtree.

Considering the same example as above the Post order is {4, 5, 2, 6, 7, 3, 1}
Once we create the root with the last element i.e 1. 

We pass the following parameters to create the left and right subtrees.

                       Inorder                 Postorder
Left Subtree    {4, 2, 5}                {4, 5, 2}
Right Subtree   {6, 3, 7}                {6, 7, 3}

Here is the C++ implementation of the above two algorithms.

Monday, September 15, 2014

Gas station problem

There are some gas stations arranged in a circle. Each of them has some amount of gas. We are also given the distances between all the consecutive stations. Assume that we have a vehicle with very large fuel tank(infinite) and one unit of gas is needed to cover one unit of distance, the problem is to find if we can complete the circuit starting at any gas station.

For example assume that we have the following data

Gas : {3, 1, 2, 5, 4}
Distance: {4, 1, 1, 2, 3}

Station[0] has 3 units of gas, 
Station[1] has 1 unit of gas and so on...

Distance between the stations are interpreted as follows
Station[0] and Station[1] is 4, 
Station[1] and Station[2] is 1, 
Station[4] and Station[0] is 3 , etc...

Let us look at the algorithm for solving this.

We can start at any possible index ( [0, n-1] ), filling all the gas at each station, and move forward if it is possible to reach next station. If we are able to reach the starting position again, We can complete the circle.

What if we are not able reach next station at some point?

For example we start at station i and reached station j and we can not proceed to station (j+1). In a naive approach we start from station (i+1) and see if we can reach station (j+1). This approach works, but it takes O(n2) time.

The catch here is that we can actually start from (j+1) because of the following reason.
If we start at any index between [i+1,j] we can not reach (j+1) since at each step in the previous iteration we had zero or more gas but still we were unable to reach j+1.

For example consider the simple instance
Gas: { 1, 1, 4}
Cost:{ 1, 2, 3} 

If we start from 0 we can reach 1 but we can not reach 2( required: 2 units, present:1 unit). If we start from 1 also, we can not reach 2. So we need not check for this index. We can start from 2 and complete the circle.

So this approach takes O(n) time.

Here is the C++ implementation.




Friday, September 12, 2014

Maximum sum of a subsequence with no contiguous elements

Given an array of positive and negative numbers, find the maximum sum of any sub sequence such that no two elements are contiguous.

For example consider the array {3,-2, 1, 7}, maximum sum is 10 for {3,7}
For {3,-2, 1, 0, -4, 2} it is 6 for {3,1,2}

This problem can be efficiently solved in O(n) time using dynamic programming technique.

The approach here is simple. We take an auxiliary array with the same size as input. 

The entries in this array are calculated as follows.

Aux[i] = Aux[i] if i = 0
       = Max( Aux[0], Aux[1] ) if i = 1
       = Max( Aux[i-2]+arr[i], Aux[i-1] ) otherwise

Here is the C++ implementation of the above approach. It takes O(n) time and O(n) space.



Tuesday, September 2, 2014

Longest substring with equal number of 0s and 1s

Given a string consisting of only 0s and 1s, How do we write a program to find the longest sub string with equal number of 0s and 1s in it?

For example consider the string "01001", the longest string with equal number of 0s and 1s is "1001".

Let us look at the solution approaches.
Considering 0 as -1 and 1 as +1, at each index we maintain a cumulative "balance" value.
 
Here balance is the difference between the count of 1 and 0 appeared so far.

For example for the example string "01001", the balance values are as follows

Index:     0   1   2   3   4
Bit:       0   1   0   0   1
Balance:  -1   0  -1  -2  -1


In this balance array, the longest distance between any two equal values gives us the required result.
 
In the above example, balance value "-1" appear at index 0 and index 4. So 4-0 = 4 is the maximum length of the sub string with equal number of 0,1s.
and the sub string is 1001 ( sub string between 1 and 4 indices).

Let us look at two possible approaches which utilizes the above property.

Method 1: Simple O(n2) approach
 
This method iterates through all possible sub strings and finds out which one is the longest with equal number of 0, 1s.
To check if a sub string has equal number of 0,1, we check the balance value at each index. If it is zero, we will update the maximum length if required.

Method 2: Efficient O(n) approach
 
This method needs extra space to run in O(n) time. For a string of length n, the range of balance values are in the range (-n, n); -n when all entries are 0, and n when all entries are 1.

We will create an array of size 2n+1 which acts as a hash table for all possible balance values. This table stores the leftmost index in the array for each balance value.


Since the array is 0 indexed, table[n+b] stores the leftmost index with balance b. At each index we keep on updating the balance value.


  • If there is no entry in the table with the given balance, we store the index for b.
  • If the table contains a previous entry with the same balance value, we check if the sub string between this previous index and the current index is the longest sub string.
Below is the C++ program to which implements the two approaches discussed above.

Monday, September 1, 2014

Longest substring with unique characters

Given a string, how do we write a program to find the length of longest sub-string without any characters repeating in it.

Let us call it a unique sub string. For example consider the string "program" the maximum length of a unique sub-string is 5 for the sub string "ogram".

A method by checking all possible sub-strings for the given property is obvious, but it is not time efficient. A naive implementation takes O(n3) time.

Let us look at more efficient approach which runs in O(n) time. Let us assume that the string contains all possible 256 ASCII characters.

We take a Boolean array of size 256 to indicate if a character exists or not.

Take two indices ind1 and ind2 initially pointing to the start of the string. As long as we find a unique character at ind2 we keep on incrementing it. Whenever we see a duplicate character , we move ind1 one index beyond the first instance of that character, keeping track of the maximum length of the sub string found so far.

For example when we find 'r' for the second time, the indices will be adjusted like the following.
p  r  o  g  r  a  m
      |     |
    ind1   ind2

Here is the C++ implementation.