Add two integers

22^nd, July 2010

Adding two integers without arithmetic operator

I heard this question multiple times, it is to judge our ability to link our understanding of digital circuits. I know, we can have some out-of-the box solutions. Given below, how I got the solution.

From digital circuits, recap that half adder can add two bits and full adder can add two bits along with carry bit, i.e. three bits. Can we augment the same logic here in software? The bitwise AND generates carry and XOR generates sum. C/C++ provides low level features to access bit level information.

Having understood the adder circuit logic, our algorithm can be depicted in the following steps,

1.     Inputs operands M and N

2.     Set sum = M XOR N

3.     Repeat the following steps until no carry

a.   Shift left the previously generated carry

b.   Save intermediate sum

c.   Update sum = sum XOR carry

4.     Stop

I have provided working code in the following links, http://ideone.com/gNi77 Try with negative numbers.

Question asked here http://geeksforgeeks.org/?p=8198#comment-1722

Find number of permutations using Stack

21^st, July, 2010

Find number of permutations

Assume we are receiving a stream of integers (1, 2, 3, 4, 5, … N). Using stack data structure (FIFO), find how many different permutations of the ordered stream is possible?

Solution: Interestingly, the answer is Catalan number.

A stack is a First In First Out data structure. The integers shall be pushed and popped in the order of their appearance in the input stream. Say, P(N) as possible permutations of the input stream. Let k representing an integer in the stream, hence the stack should contain k-1 elements and N-k-1 elements are in pipeline from the stream.

Fixing k position, the k-1 elements can be pushed and popped in (k-1)! ways. Similarly, the upcoming N-k-1 elements. In other words, there are P(k) permutations possible with the elements in the stack and P(N-k-1) permutations are possible with the upcoming integers. But, k can range from 1 to N, using multiplication and addition principle we get,

P(N) = ∑ P(k-1)P(N-k-1), k ranging from 1 to N, and P(1) = 1.

The expression P(N) is recursive. After expanding, we get Segner’s expression which can be represented in Catalan number.

P(N) = (2NcN)/(N+1) – Catalan Number C(N)

The above expression resembles the Catalan number. The Catalan numbers are ubiquitous.

Note that there are N! possible permutations using N integers, however, P(N) < N!. It is due to the definition of stack data structure.

Probability and Lagrange Identity

20^th July, 2010

Find the probability of meeting A and B.

Given a Cartesian plane as shown in the figure. Consider person A, initially at the origin and person B initially at the point (n, n) wants to meet. At each point (x, y), each one flips a coin and decides the next move; A moves up side on ‘Head’ and right side on ‘Tail’ to the next point, whereas B moves downward on ‘Head’ and left side on ‘Tail’ to the next point. Find the probability that they will meet within the square lattice.
Solution:

Say each point is one unit length. If A and B met, they must travel n points on total by both and meet on the diagonal at some point P. Let us assume, A traveled k units then B must travel (n – k) units. Hence they meet at point P(i, n − i), where 0 ≤ k ≤ n.

A has nCk possible ways from the origin where as B has nC(n – k) possible ways from point (n, n). Per multiplication principle, the total possible ways are (nCk) x ( nC(n – k) ). However, k can range from 0 to n. Summation of the product over possible values of k will give us the number of ways A and B can meet.

i.e. No of ways to meet = Sigma [(nCk) x ( nC(n – k) )], where 0 ≤ k ≤ n.

Simplified using Pascal identity, = Sigma [(nCk) x (nCk)], where 0 ≤ k ≤ n. Since, nCk = nC(n-k)

= Sigma [(nCk)]² , where 0 ≤ k ≤ n.

= 2nCn, Lagrange Identity

We are half done. What would be the total sample place? For each person A and B, it is possible to take 2ⁿ ways (sum of binomial coefficients). It means total sample space is 2²ⁿ. So, it is easy to find the probability.