Thursday, September 8, 2016

LeetCode OJ - Elimination Game

Problem:

Please find the problem here.

Analysis:

I experimented with the judge, it gives very big number as input (e.g. 10000000), therefore direct simulation of the game is not the way to go.

I have stuck for this problem for a good while, but a key observation saved me, by looking at the game in binary notation.

Suppose we are playing the game with input 9, here is how to elimination process go

First round

0001
0010
0011
0100
0101
0110
0111
1000
1001

The first round eliminate all the odd numbers, no surprise there, we already know. The key one is the next elimination, let's see:

0010
0100
0110
1000

The key observation here is that the second (least significant) bit of the crossed number is always 0. Think about it, it has to be, because we are now crossing every other one. Here is the last round.

0010
0110

This one is not obvious, but one can argue the third (least significant) bit of the crossed number must be 0.

Solution:

With that observation, now we can derive a solution. The first (least signficant) bit must be 0 because we crossed out all the odd numbers. The second (least signficant) bit must be 1 because we crossed out all the 0, and so on.

Therefore the key to the puzzle is to find out which bit is crossed out and output the other bit. To determine that, just find out the corresponding bit of the number that is crossed out first, to do that, all we need to do is to maintain the begin and the end to the array. With the begin and end, we can determine the corresponding bit in constant time, and therefore, we are constructing the solution in $ O(number of bits) $ time, that is bounded by $ O(\log n) $, much faster than direct simulation.

Note that in the code, to make it easy to code, I simply shifted away the least significant bits once I have done with computing that. This make it easy for me to extract the corresponding bit.

Code:

#include "stdafx.h"

// https://leetcode.com/contest/2/problems/elimination-game/

#include "LEET_ELIMINATION_GAME.h"
#include <stack>
#include <iostream>
#include <sstream>
#include <vector>
#include <string>

#include <stdio.h>

using namespace std;

namespace _LEET_ELIMINATION_GAME
{
    class Solution
    {
    public:
        int lastRemaining(int n)
        {
            return lastRemaining(1, n, 0);
        }

        int lastRemaining(int smallest, int largest, int round)
        {
            if (smallest == largest)
            {
                return smallest;
            }
            if (round % 2 == 0)
            {
                if (smallest % 2 == 0)
                {
                    // Eliminate all 0
                    smallest += 1;
                    if (largest % 2 == 0) { largest -= 1; }
                    return lastRemaining(smallest >> 1, largest >> 1, 1) * 2 + 1;
                }
                else
                {
                    // Eliminating all 1
                    smallest += 1;
                    if (largest % 2 == 1) { largest -= 1; }
                    return lastRemaining(smallest >> 1, largest >> 1, 1) * 2;
                }
            }
            else
            {
                if (largest % 2 == 0)
                {
                    // Eliminate all 0
                    largest -= round;
                    if (smallest % 2 == 0) { smallest += 1; }
                    return lastRemaining(smallest >> 1, largest >> 1, 0) * 2 + 1;
                }
                else
                {
                    // Eliminating all 1
                    largest -= round;
                    if (smallest % 2 == 1) { smallest += 1; }
                    return lastRemaining(smallest >> 1, largest >> 1, 0) * 2;
                }
            }
        }
    };
};

using namespace _LEET_ELIMINATION_GAME;

int LEET_ELIMINATION_GAME()
{
    Solution solution;
    cout << solution.lastRemaining(10000000) << endl;
    return 0;
}

1 comment :