Monthly Archives: May 2014

Generating Gray codes

Gray code is a sequence of n-bit binary code where each pattern differs with the previous pattern by only one bit.

For example 2-bit gray code is shown below.

00
01
11
10

Now we have two write a program to generate such a sequence for the given value (n). One algorithm to generate gray code is explained below. An n-bit gray code can be generated from (n-1) bit gray code as follows.

1-bit gray code is obvious; it is 0,1.
2-bit gray code can be generated as follows. 
  • Expand the sequence by adding it’s elements in reverse order (in this case 1, 0).
  • Prepend zeros to the first half and Ones to the second Half

 0  0
 0  1
 —–
 1  1
 1  0

3-bit gray code can be generated similarly.

0  00
0  01
0  11
0  10
——
1  10
1  11
1  01
1  00

Below is the implementation of this algorithm in C++.

Generating the counting sequence

Given an integer N, we have to generate the nth sequence of the following pattern.
  • “1”
  • “11” as the previous item contains one instance of 1.
  • “21” as the previous entry contains two 1’s.
  • “1211” as the previous entry contains one 2 and one 1.
Following is the program which generates such a sequence. It runs in O(n*k) (where k is the length of the sequence) time and it utilizes only constant extra space.

Finding the integer square root of a number

How do we implement a function to find the integer square root of a number?

For example int_sqrt(4) = 2, int_sqrt(10) = 3. (We have to take floor of the actual square root)

A simple method is to iterate i from 1 to N/2 and keep checking until i2 < N, and whenever i2 >= N return i.

for( int i = 1; i <= N/2 ; i++ )
{
    if( i*i >= N )
        return i;
}

But this algorithm takes O(n) time. For large numbers this takes a lot of time. Any way to improve this further?

Binary search comes to our rescue. we start with the initial range [0, N]. In each iteration we check if mid2 <= N and (mid+1)2 >N. If this is satisfied, we return mid.

If mid2 > N, we confine our search to the left half; otherwise we search in the right half.

This implementation takes only O(log N) time.

Here is the C++ implementation. 



Setting the matrix elements to zero

Given a matrix of size m * n, write a program to fill zero in ith row and jth column if matrix[i][j] is zero.

For example let us consider the following matrix.

  6 0 2
  1 3 4
  5 9 0
]
It should transform to the following.
  0 0 0
  1 0 0
  0 0 0
]

This problem looks simple at the first glance, but if we do not write the program carefully it results in the wrong output, typically marks all the elements in the matrix to zeros.

So a wrong solution can be iterate through all the elements of a matrix, and whenever we found a zero, set the corresponding rows and columns as zero.

This will have undesired effect. Since we are modifying the same matrix, it is possible that an unexplored element may be set to zero because of a zero in the same row or column. So it is not possible to solve this problem in just one iteration.

An inefficient, but correct solution could be to create a temporary matrix which is a copy of the original matrix, and mark the elements in temp instead of the original. This will take O(m*n) extra space.

Can we solve this more efficiently?

One possibility is to first go through all the elements in the matrix and store the zero containing row and column indices into two sets.

Then set all the elements in the corresponding rows and columns to zeros in the next step. This approach will only take O(m+n) space, an improvement over the previous. Any solution should take O(m*n) time because we have to iterate through all the elements of the matrix at least  once.

Here is the C++ function which takes the matrix as input and modify it.