Skip to content

Coconuts, Revisited (616)

September 14, 2014

Problem statement

The maximum people number must be less than sqrt() of given coconut number n, so maximum people <= (int)sqrt(n);


int result = 0;

— For i = (int)sqrt(n) to 2

—– if (n % i == 1)   

———  result = calculatePeople(n, i, i);

——if (result != 0)

———– break;

if (result != 0)

—print(“Solution”);

else

—print (“No Solution”);


int calculatePeople(int m, int i, int k)

{    

     //Termination Condition

       if ( k == 1 &&  m%i  == 1)

             return i;

//Calculate updated m after a person taking his share + giving 1 to monkey.

      m = (m/i) * (i -1);

     int result;

      //Now Check if (m /%(i -1) == 1)?

            if  condition true

                 result = calculatePeople(m, i , k -1);

                 return result;      

          else

               return  0

}


By recursively calling this method you will get the correct result. if the function return any value except 0, that means it has a solution with number of people same as return value.

Lets go with first example in sample dataset.

n= 25.

i = 5 to 2;

i = 5 ,

       –> n = 25

       –>  doesn’t meet n%i == 1.

i = 4,

      –> n = 25

      –> meet (n%i) == 1.

      –> Call calculatePeople()

      –> m = 18

      –>  doesn’t meet m%i == 1.

      –> return 0, means no solution exist with i =4

i = 3

      –> n = 25

      –> meet (n%i) == 1.

      –> Call calculatePeople()

      –> m = 25  k = 3

      –> meet (m%i) == 1.

      –> m = 16   k = 2

      –> meet (m%i) == 1.

      –> Call calculatePeople()

      –> m = 10  k = 1

      –> k = 1  && (m%i) == 1.

           –>return i = 3

Advertisements
No comments yet

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: