Euclidean Algorithm at Pizza Place

Few days back, I went to a Pizza Place along with my girl-friend.Something was strange about this place.When the waiter was taking the order he asked us our respective age.We thought there must be some special offer for different age group so we gave him our ages.After sometime he got us a very tasty pizza.Wow! this place serves best pizza in the world.This place should be in Italy.

Normally pizza is cut into 2 or 4 pieces for 2 people.But this pizza was cut into 15 pieces,How can I equally share this pizza with my girl-friend.So I had to eat 8 pieces and left remaining 7 for my girl-friend.

Unlike my thought,no special discount was given to us,I had to pay whole bill (including taxes :( ).Thing which was bothering me was why the waiter asked us for our age and why pizza was cut in unusual manner.I asked manager of the place to clear my doubts,but he said its a secret and cant share it with anyone.

Restless and eager to know the relation between ages and no of pieces,So i visited the place again to find the relation.

Now this time we gave him our false ages and no of pieces in which pizza was cut was also different this time.I kept on revisiting the place to get the pattern and also pizza was really tasty.

I compiled following information while visiting the place

Information :

My Age  | My GF Age     | No of Pieces
------------|--------------------|-----------------
  24         |  21                   |  15
  44         |  28                   |  18
  23         |  17                   |  40 

From above data,
Lets consider 1st case :
Ages can be divided by 3 


Ans == >  My age = 8
               + GF age = 7 
                                 15 = No of pieces (Last Column)


2nd case : 
Lets divide Ages by 2

Ans == >  My age = 22

               + GF age = 14

                                 36 = No of pieces / 2 

Ages can be further divided by 2,which gives us,

Ans == >  My age = 11

               + GF age = 7

                                 18 = No of pieces (Last Column) 

3rd case : 

Ans == >  My age = 23

               + GF age = 17

                                 40 = No of pieces (Last Column) 

As both numbers are prime there is no common factor.

So it seems that we found the secret of Pizza Place.They divide the number until both numbers have a common factor and then they just add the numbers and cut pizza into that many pieces.

So its a problem of finding Greatest Common Divisor (GCD).
So how to find GCD of two given numbers.

Here is the algorithm
1. Start
2. Min = Minimum (a,b)
3. Loop till min >= 1
4. if(a % min == 0 && b % min == 0 )
     return min;
5. return 1; 


Code :


    public int gcd(int a,int b) {
        for(int i = Math.min(a, b); i >= 1; i--) {
           if( a % i == 0 && b % i == 0) {
               return i;
           }
}
return 1;
    }

The above solution just loops backwards from Min till 1 and checks whether both numbers can  be divide equally with the loop counter.
If yes, then we have our GCD Else it returns 1;

But what if  numbers are very large e.g  prime near to 10^6 and prime near 10^5 and less than 10 ^ 6.
In this case as both numbers will be prime numbers their GCD will be 1.

Above solution will take more time to return GCD for such large numbers.

So lets take another approach which is called Euclidean_algorithm to find GCD.
this algorithm is nothing but a recursive technique to find GCD of given two numbers.

Recursive function :  


gcd(a,b)    =    a                                                ...if b = 0 
                 =   gcd(b,remainder(a,b))              ...if a > b, b > 0


Code : 


    public int gcd(int a,int b) {
        if(b == 0) return a;
return gcd(b,a%b);
    }

Above recurrence reduces the problem in each step,thus we get GCD in fewer steps.

**GCD's are also helpful in finding Minimum Fraction (or Smallest Ratio).

So we have revealed the secret of Pizza Place and also learnt how to find GCD through programming.
Bye for now, Happy reading. :)