Q: Find the greatest common divisor of 2 numbers a and b and also find 2 numbers x and y such that ax + by = GCD(a,b)

Solution:

Every number is divisible by 1, and so the least common divisor of a pair of numbers is 1. The more challenging problem is to find the Greatest Common Divisor (GCD), the largest divisor common to a set of given integers.

The naive way of finding the GCD is to find all divisors of one number and test each of these for divisibility on the second. Another way would be to find the prime factorization of both numbers and find product of all common factors. But, as you can see, these methods are more brute-force and will be computationally intensive.

Euclid’s algorithm for GCD computation was one of the earliest interesting algorithms in history. It is based of a couple of basic observations.

1. If b divides a, then GCD(a,b) equals b

2. If a = bn + k, then GCD(a,b) = GCD(b,k)

The first observation is pretty straight forward. If b divides a, then a = bn where n = 1,2,3.. and so GCD(a,b) = GCD(bn,b) = b

For the second observation, GCD(a,b) = GCD(bn+k, b) Any common divisor of a and b is now dependant on k, since bn is divisible by b.

From this you see that the algorithm is recursive. Replace the bigger integer by its remainder mod smaller integer. This basically cuts down the integer size to at least half for each step, and thus the running time of the algorithm is logarithmic number of iterations to the naive ones discussed above.

An outcome of Euclid’s algorithm is that you can find more than just the GCD(a,b). In fact you can also find two integers x and y such that

ax + by = GCD(a,b)

int GCD(int a, int b, int& x, int& y)
{
      int prevX, prevY;
      int gcd;

      if(b > a)
      {
      return GCD(b,a,y,x);
      }

      if(b == 0)
      {
            x=1;
            y=0;
            return a;
      }

      gcd = GCD(b, a%b, prevX, prevY);
      x = prevY;
      y = prevX - FLOOR(q/b) * prevY;
      return gcd;
}

Q: You are given two singly linked lists, such that they start from two different nodes (head) and then, a few nodes down the list, they meet at a common node and then share all the nodes henceforth until the tail. The task is to find the first common node.

Solution:

There are a few ways to solve this. The trivial solution would involve storing all the nodes of the smaller list and traverse each node in the bigger list, comparing each node to the already stored nodes. Instead of storing the nodes you can traverse the whole (smaller) list each time. It is clear however, the each of these are inefficient (time and space)

—————————————————————————————-

Here’s another way to do this. Much more efficient but requires modifying the original list

Let list L1 have ‘a’ number of nodes leading to the intersecting node and ‘k’ number do nodes afterwards;

a+k=len1 –> equation 1

Let list L2 have ‘b’ number of nodes leading to the intersecting node and ‘k’ number do nodes afterwards;

b+k=len2 –> equation 2

You can calculate len1 and len2 by traversing the list

subtracting the above 2 equations you get

a-b= len1-len2; –> equation 3

Now reverse List 2 and then traverse from the head of List 1 and count the number of nodes as you go, you will eventually reach the original head of List 2. Let the length you just computed be len 3

a+b = len 3 –> equation 4

You have 2 equations (3 and 4) and 2 unknowns (a and b)

a and b are the lengths of list from the head of each list to the intersecting node.

You can re-reverse List L2 to revert it to the original state

—————————————————————————————-

Sometimes you do not want to alter the start of list. In multithreaded applications, other threads could be reading from the list and Locking leads to performance issues. The following solution will solve the problem without actually altering the list

First, Traverse the 2 lists and find their lengths (L1 and L2). Traversing the longer list starting from its head until you move (L1-L2) nodes. At this point both the nodes are equidistant from the first intersecting common node. Now Traverse both the list one node at a time and compare the nodes at each step until you find a match. This matching node is the intersecting node.

—————————————————————————————-