Solving Egg Dropping Puzzle

The standard solution for finding the minimum number of drops for N floors and M eggs is already covered on many websites.In this blog , I will cover a different result,i.e,Finding recurrence relation to the  maximum number of floors which can be covered using a given number of eggs and drops.

We have  M eggs, N drops ,
g[m][n] denotes the maximum number of floors which can be covered using the above.

Reccurence Relation:

g[m][n] = g[m-1][n-1] + g[m][n-1] + 1


Base Cases :-

1)g[m][0] = 0           | With 0 drops , 0 floors can be covered

2)g[1][m] = m          | With m drops , 1 egg -> only m floors can be covered.This is because we only have                                     the option of dropping the only egg from 1st floor , if it breaks we are done , else                                           (m-1) floors above can be covered.


Some general solutions:

1)g[2][n] = (n+1)C2
2)g[3][n] = (n+2)C3 and so on...

Explanation:

For m eggs , and n drops 

We know that we can cover g[m-1][n-1] floors using (m-1) eggs and (n-1) drops. Hence we will drop mth egg from (g[m-1][n-1] + 1)th floor , because if the egg drops we are left with (m-1) eggs and (n-1) drops, which can cover g[m-1][n-1] floors(as per definition). Now , if the mth egg doesnt breaks , then we are left with m eggs, (n-1) drops which can cover g[m][n-1] floors , So in total we dropped from (g[m-1][n-1] + 1)th floor, and g[m][n-1] floors above can also be covered, which gives us
g[m][n] = 1 + g[m-1][n-1] + g[m][n-1].

SPOJ MULTII

Problem Link : http://www.spoj.com/problems/MULTII/

Solution:

The problem is easy , once we see it as a graph . Consider a graph with vertices representing remainders (0 - (N-1) ). Initially we have only { d1%N,d2% N , .. dk%N } vertices , that can be reached . Now from each of these vertices , we can go to (10*k1 + k2)%N , where k1 is any vertex , and k2 is a digit belonging to that subset. So just do a BFS/DFS on this graph to see if vertex with remainder 0 can be reached or not !

Example : suppose we have only 7,8,9 that we can be used , and N = 11. Then from 7 we can go to
7*10+8%11 = 1 , 7*10 + 9 = 2 , 7*10 + 9 = 3, 8*10 + 7 = 10 , 8*10 + 8 = 0 . Hence we reach the state 0 .

Complexity will be O(10*N).

Add Two Numbers Represented By Linked Lists Without Recursion, Stack In O(n)

Given two numbers represented by two linked lists, write a function that returns sum list. The sum list is linked list representation of addition of two input numbers. It is not allowed to modify the lists. Also, you cannot use explicit extra space OR stack OR recursion.

Example : 

Input:
  First List: 5->6->3  // represents number 563
  Second List: 8->4->2 //  represents number 842
Output
  Resultant list: 1->4->0->5  // represents number 1405 

This problem was asked in Microsoft Internship Interview at my campus.

The solution for the above problem is available on many websites some of which include geeksforgeeks, stackoverflow , some blogs ,etc. However, the solution that they have given do involves recursion or reversing linked lists and then adding or using stack.

But if we observe carefully , we don't actually need any extra memory in this case . Firstly because we know that the carry in this addition cannot be more than 1. This simplifies things a lot.

Coming  to the algorithm , since we are moving in the reverse direction of addition in this case , we would need to know for every position , the information that will there be any carry from the next position or not . So every position we will evaluate the carry from the next position .

As in the above example : 5 + 8 = 13 , we need to know if the actual answer will be 13 or 14 , and to do that we will see the next node and so on.

Checking this is actually easy as we will keep moving ahead from the node next to the current node and stop once if the sum of the nodes is <= 8 or >= 10. In both these cases , we know the carry , in sum <= 8 , carry is 0 , and if sum >= 10 , carry = 1 . So the only case that will keep us moving is sum = 9. This is because this case is doubtful , we still don't know if there will be carry from the right side.

So by following this , we will come to know for a position if there will be a carry or not . And accordingly we can update our node  , and then update the nodes right to it , which we traversed to know the carry. This way we evaluate whole of the answer. Implementation is a bit tricky and you will need to be careful for handling all the cases.

I implemented the above algorithm in C ,and here is my code .If you find any bugs in the code or algorithm, feel free to comment.

Code : 

struct t_node{

    int data;

    struct t_node *next;

};

typedef struct t_node node;

node* newNode(int data){

    node *t = (node *)malloc(sizeof(node));

    t->data = data;

    t->next = 0;

    return t;

}

node* insert(node *head, int data){

    if(!head){

        return newNode(data);

    }

    else{

        head->next = insert(head->next, data);

        return head;

    }

}

void print(node *head){

    if(head){

        printf("%d ",head->data);

        if(head->next) printf(" -> ");

        print(head->next);

    }

}

node* add(node *h1, node *h2){

    int s = h1->data + h2->data;

    node* ans = 0;

    if(h1->next == 0){

        if(s >= 10) ans = insert(ans,s/10);

        ans = insert(ans,s%10);

        return ans;

    }

    node *head_ans = 0;

    h1 = h1->next , h2 = h2->next;

    while(h1){

        node *t1 = h1, *t2 = h2;

        int l = 0;

        while(t1){

            int sum = t1->data + t2->data;

            if(sum <= 8){

                l = 1;

                break;

            }

            else if(sum >= 10){

                l = 2;

                break;

            }

            t1 = t1->next ;

            t2 = t2->next ;

        }

        if(l == 2) ++s;

        if(head_ans == 0){

            if(s >= 10) ans = insert(ans,s/10);

            ans = insert(ans,s%10);

            head_ans = ans;

            if(s >= 10) ans = ans->next ;

        }

        else{

            ans->data = s;

        }

        node *l1 = h1 , *l2 = h2;

        if(l == 0 || l == 1){

            while(l1){

                int sum = l1->data + l2->data;

                ans->next = newNode(sum);

                ans = ans->next;

                if(l1 == t1) break;

                l1 = l1->next , l2 = l2->next;

            }

            if(!l1) return head_ans;

            else l1 =  l1->next , l2 = l2->next;

        }

        else{

            while(1){

                if(l1 != t1){

                    ans->next = newNode(0);

                    ans = ans->next;

                    l1 = l1->next , l2 = l2->next;

                }

                else{

                    int sum = l1->data + l2->data;

                    ans->next = newNode(sum%10);

                    ans = ans->next;

                    l1 = l1->next , l2 = l2->next;

                    break;

                }

            }

        }

        h1 = l1 , h2 = l2;

        s = ans->data;

    }

    return head_ans;

    ///~

}

int main(){

    int n1, n2, x;

    node *list1, *list2;

    list1 = list2 = 0;

    scanf("%d%d",&n1,&n2);

    while(n1--) scanf("%d",&x), list1=insert(list1, x);

    while(n2--) scanf("%d",&x), list2=insert(list2, x);

    puts("") ;print(list1);

    puts("") ;print(list2);

    puts("");

    node *ans=add(list1,list2);

    print(ans);

    return 0;

}