## Sunday, August 9, 2015

### Detecting the loops in a linked list

Hello Friends today I want to take one of the question that one of my friend asked me which he faced in an interview.

How would you detect whether the linked list has the loop or not?

Let us take a basic example, so assume you have the linked list like that looks like this:

A -> B -> C -> D ->B

Now if you look at the list you find out that the last node is pointing towards B. So now the question is how would you find whether the list has a loop or not.

For this problem there are some solutions, one of them is Floyd's cycle-finding algorithm, also known as tortoise and hare algorithm.

The algorithm's idea is that, maintains 2 pointers and move with them with different speeds, one fast and one slow, if there is a loop, one time they will definitely meet.

Going forward with this idea in mind, let us see the program.

```boolean hasLoop(Node first) {
if (first == null) // list does not exist..so no loop either.
return false;
Node slow, fast; // create two references.
slow = fast = first; // make both refer to the start of the list.
while (true) {
slow = slow.next;          // 1 hop.
if (fast.next != null)
fast = fast.next.next; // 2 hops.
else
return false;          // next node null => no loop.

if (slow == null || fast == null) // if either hits null..no loop.
return false;
if (slow == fast) // if the two ever meet...we must have a loop.
return true;
}
}
```

Now the other problem is to know the start of the loop. For that we follow:

Step1: Proceed in the usual way u'll use to find the loop. ie. Have two pointers, increment one in single step and other in two steps, If they both meet in sometime, there is a loop.

Step2: Freeze one pointer where it was and increment the other pointer in one step counting the steps u make and when they both meet again, the count will give u the length of the loop.(This is same as counting the number of elements in a circular link list.)

Step3: Reset both pointers to the start of the link list, increment one pointer to the length of loop times and then start the second pointer. increment both pointers in one step and when they meet again, it'll be the start of the loop. (This is same as finding the nth element from the end of the link list.)

Working code here

```public class LoopInLinkedList {

static class Node {
public String info;
public Node next;
@Override
public String toString() {
return "Node [info=" + info + ", next=" + next.hashCode() + "]";
}
}
public static void main(String[] args) throws Exception {

Node n1 = new Node();
n1.info = "A";
Node n2 = new Node();
n2.info = "B";
Node n3 = new Node();
n3.info = "C";
Node n4 = new Node();
n4.info = "D";
Node n5 = new Node();
n5.info = "E";
Node n6 = new Node();
n6.info = "F";
Node n7 = new Node();
n7.info = "G";
Node n8 = new Node();
n8.info = "H";

n1.next = n2;
n2.next = n3;
n3.next = n4;
n4.next = n5;
n5.next = n6;
n6.next = n7;
n7.next = n8;
n8.next = n2;

detectLoop(n1);
}
public static boolean detectLoop(Node start) throws Exception {
Node slow = start;
Node fast = start;
while (slow !=null && fast != null) {
slow=slow.next;
fast=fast.next.next;
if (fast == slow) {
int k = getLengthOfLoop(fast);
Node startOfLoopNode = detectLoopStart(start, k);
System.out.println("Length of the loop is " + k);
System.out.println("Start of the loop is " + startOfLoopNode);
return true;
}
}
return false;
}
private static int getLengthOfLoop(Node loopNode) throws Exception {
Node ptr = loopNode;
int k=0;
while ((ptr=ptr.next)!=loopNode) {
k++;
}
return k+1;
}
private static Node detectLoopStart(Node start, int k) throws Exception {
Node ptr1 = start;
Node ptr2 = start;
while (k-->0 && (ptr1 = ptr1.next)!=null);
while ((ptr1=ptr1.next)!=null && (ptr2=ptr2.next)!=null && ptr1 != ptr2);
return ptr1;
}
}
```

### Getting the sum of all multiples of 3 and 5 before a number n

Hello all, today we are going to look on to a problem that says the total of all the multiples of 3 and 5 before a number n.

Note: Before n

So  if I say take the sum of all numbers before 10 which are the multiples of 3 and 5 then the answer would be: 3,5,6,9 and the answer would be 23 (3+5+6+9).

Before going to the implementation lets go back and make some points:
1. The multiples of 3 and to make a sum of them would be:
• 3 + 6 + 9 + 12 + 15 ...... which cuts down to : 3 * (1 + 2 + 3 + 4 + 5 ......). Now if you look at this series it is an Arithmetic Progression or you can say that it is the sum of n natural numbers, multiplied by 3.
• Now the second part which is quite important to notice is that if I say that you have to add all the multiples of  3 before 10 (excluding 10) then then total numbers to be added is 3 * (1 + 2 + 3), which means that the n-1(since we don't have to include n)(for us ,10-1, 9) is divided by 3 and then we consider it to be the part where we can say that apply the formula of addition of first n natural numbers multiplied by 3.
• So in total the formula would be 3 * (sum of first (n-1)/3 natural numbers), this part is a bit tricky so please give more attention to it.
2. Same will be the case of numbers divisible by 5 as well.
3. One more important thing is that if the n is 16 and we have to add all the multiples of 3 and 5 together then the answer would be:
(3 + 6 + 9 + 12 +15) + (5 + 10 + 15)
if you notice the expression the digit 15 is added twice since, 3 & 5 both are the multiples of 15 and so added twice.
4. Now in order to do correct solution we have to remove the digits those are the multiple of 15(i.e 3*5)
5. So the case would be like this:
3 * (sum of first (n-1)/3 natural numbers)
5 * (sum of first (n-1)/5 natural numbers)
15 * (sum of first (n-1)/15 natural numbers)
Now lets prepare the code :

```public class Solution {
public static Scanner ins = new Scanner(System.in);
public static sumOfNNaturalNumbers(int n) {
return (n*(n+1)/2);
}
int result = ins.nextInt();
ins.nextLine();
return result;
}