Josephus Problem!

You're forced to commit suicide, and you will use math to save yourself!

weird, huh? but this actually happened. Quoting from Wikipedia:

"The problem is named after Flavius Josephus, a Jewish historian living in the 1st century. According to Josephus' account of the siege of Yodfat, he and his 40 soldiers were trapped in a cave, the exit of which was blocked by Romans. They chose suicide over capture and decided that they would form a circle and start killing themselves using a step of three. Josephus states that by luck or maybe by the hand of God, he and another man remained the last and gave up to the Romans."

Problem Statement

There are people standing in a circle waiting to be executed. The counting out begins at some point in the circle and proceeds around the circle in a fixed direction. In each step, a certain number of people are skipped and the next person is executed. The elimination proceeds around the circle (which is becoming smaller and smaller as the executed people are removed), until only the last person remains, who is given freedom. The task is to choose the place in the initial circle so that you are the last one remaining and so survive.

so how can we solve this problem?

We'll consider the case where we repeatedly execute the second person in the circle (k = 2) in a circle of size N. We want to find the position of the person who will be the last to execute himself, but of course he wouldn't, he would like to survive!

let's see the case for N = 1, Solution = 1 as this is the only person in the circle.
for N = 2, Solution = 1, as the second person will execute himself and "1" remains.

for N = 3, we have circle = (1, 2, 3). 2 will execute himself, then we're now standing at "3" as the first element and we have circle = (1, 3). the second person will execute himself "1", then the survivor is "3".

for N = 8, we have circle = (1, 2, 3, 4, 5, 6, 7, 8).

in the first run, "2", "4", "6" and "8" will all be executed and we'll end up with (1, 3, 5, 7).
we repeat again, "3" and "7" will be executed". we now have "1" and "3". "3" will be executed, now we have "1" as the survivor.

here is a list of the results for some N.

N = 1, S = 1
N= 2, S = 1
N = 3, S = 3
N = 4, S = 1
N = 5, S = 3
N = 6, S = 5
N = 7, S = 7
N = 8, S = 1

How can we solve this with code?

Trivial solution is to model the group as a circular linked list and repeatedly delete every second element until the size of the list is zero.

Code for this is something like

typedef struct Node
{
   int value;
   Node *pNext;
} Node;

int josephus(int N)
{
   Node *head, *curr;
   // Error case
   if(N <= 0)
      return -1;

   // Create a circular list of people with
   // 1 -> 2 -> 3 -> .... -> N -> 1
   curr = head = new Node();
   head->value = 1;

   for(int i = 2; i <= N; ++i)
   {
         curr->pNext = new Node();
         curr = curr->pNext;
         curr->value = i;
   }

   curr->pNext = head;

   curr = head;
   // While not everyone is dead
   while(N > 1)
   {
      Node *tmp = curr->pNext;
      curr->pNext = tmp->pNext;
      delete tmp;
      curr = curr->pNext;
      --N;
   }

   return curr->value;
}

This is an O(N) time complexity solution and also O(N) space. Can we do better?
Yes!

With a few observations, if we have a circle of size (2 * N), meaning that it has an even number of people, like (1, 2, 3, 4, 5, 6). After the first run, "2", "4", "6" are eliminated and we have "1", 3", and "5". A circle of size "3" where each person id is multiplied by "2" then "1" is subtracted from it.

So, in order to find the solution of a circle with size N where N is even, we simply find the solution of circle (N/2) then multiply it by "2" and subtract "1".

in other means, S(N) = 2 * S(N-1) - 1, where N is even.
What if we have a circle of odd size?

(1, 2, 3, 4, 5, 6, 7) let's say it's of size (2 * N + 1).

After the first run, "2, 4, 6" are deleted which eliminates the "N" part, we then need to eliminate one more item to get to the smaller subproblem, so the next element to be eliminated is "1".

We end up with "3, 5, 7". Comparing it to "1, 2, 3". we see that each element is multiplied by "2", then added to "1"

so the total recurrence is:

S(N) = 2 * S(N/2) - 1, where N is even
S(N) = 2 * S(N/2) + 1, where N is odd

We can simply write a recursive solution for this with the base case of N(1) = 1, the complexity of this solution is O(lg N) as it divides the size of problem by two.

code for this can be something like

int josephus(int N)
{
   if(N <= 0)
      return -1;
   else if (N == 1)
      return 1;
   else
   {
      // testing the least significant bit to know
      // if this is an odd number
      if(N&1)
         return 2 * josephus(N/2) + 1;
      else
         return 2 * josephus(N/2) - 1;
   }
}

Can we do better than O(lg n)? Yes we can!
Let's see some other simple observations

N = 1, S = 1
N= 2, S = 1
N = 3, S = 3
N = 4, S = 1
N = 5, S = 3
N = 6, S = 5
N = 7, S = 7
N = 8, S = 1
N = 9, S = 3
N = 10, S = 5
N = 11, S = 7
N = 12, S = 9
N = 13, S = 11
N = 14, S = 13
N = 15, S = 15.

You can see that at every power of "2", solution resets to "1" then, "2" is added repeatedly till we reach the next power of 2. This can be proved by mathematical induction. So one way to solve this is the following:

if M is the biggest power of "2" that is less than or equal to N, let L = N - M;
Now multiply L by 2 as we're adding "2" at every step, then finally add "1". The result will be S = 2 * L + 1.

let's see some example
for N = 14, the last power of "2" is "8", set L = N - 8 = 6;
S = 2 * L + 1 = 13!

how can we find the last power of "2" greater than or equal to N? this is simply the leftmost set "1" bit in N if we represent it in binary.

Now, how can we write code for this in O(1)? it should be something like this:

This code will work if int is 32-bit size. It's called bit smearing and is used to find the left-most "1" bit, we're then going to reset it and that will simply subtract the power of two from the number.
we'll then shift it left by "1" to multiply it by two and add "1".

int josephus(int n)
{
   int m = n;
   if(n <= 0)
      return -1;
   m |= (m >> 16);
   m |= (m >> 8);
   m |= (m >> 4);
   m |= (m >> 2);
   m |= (m >> 1);
   m ^= (m >> 1);
   n &= ~m;
   return (n << 1)|1;
}

You can search or think of solutions for the general case when k != 2.


See you soon...

TopCoder BiggestRectangleEasy

This is an easy problem, but can be solved with short code using bit-wise binary operators, and as I'm always a big fan of binary tricks, I decided to post it here.

Problem Statement

Little Josh has found several sticks that are each 1 inch long. He wants to form a rectangle with the biggest possible area, using these sticks as the perimeter. He is allowed to glue sticks together, but he is not allowed to break a single stick into multiple shorter sticks. For example, if Josh has 11 sticks, he can create a 2 x 3 rectangle using 10 sticks. This rectangle has an area of 6 square inches, which is the biggest area that can be achieved in this case. You will be given an int N, and you must return the maximal area (in square inches) of a rectangle that can be created using N or less sticks.

so how can we solve this problem?

Let's see what we can do. First if the number of sticks is odd, we have to remove one stick as there can't be a rectangle with an odd perimeter. We have a rectangle with a perimeter N, and we all know that the perimeter of a rectangle is 2 * (rectangle's width + rectangle's height).

suppose width is "w" and height is "h", we divide by "2" to get sum = "w + h".

Now, we want to maximize "w * h" and we already have sum = "w + h".
one way to find "w" and "h" that maximize the product, is to try with "w" = 1 and h = "sum - 1" then store their product, then keep increasing "w" and decreasing "h" to find the values that will maximizes their product.

So this will give us a linear-time solution in terms of "w + h". A simple observation however, is that in order to maximize "w * h", "w" and "h' have to be as close as possible (I don't know a mathematical proof for that, if you know one please post it here". So, we simply set "w" = sum/2 and "h" = sum - w, and we have the maximum area that we can have with N sticks!.

Now let's see code for this.

int findArea(int N)
{
   // If the number of sticks is odd, remove one.
   // Divide by 2 to get "w+h"
   N >>= 1;
   // set "w" to "N/2"
   int w = N >> 1;
   // return "w * h"
   return (w * (N - w));
}