New Problem Solution "Elimination Game"

haoel · haoel · commit a4b191a6451e · 2016-09-08T01:36:50.000+08:00
diff --git a/README.md b/README.md
@@ -8,6 +8,7 @@ LeetCode
 
 | # | Title | Solution | Difficulty |
 |---| ----- | -------- | ---------- |
+|390|[Elimination Game](https://leetcode.com/contest/2/problems/elimination-game/) | [C++](./algorithms/cpp/eliminationGame/EliminationGame.cpp)|Medium|
 |389|[Find the Difference](https://leetcode.com/problems/find-the-difference/) | [C++](./algorithms/cpp/findTheDifference/FindTheDifference.cpp)|Easy|
 |388|[Longest Absolute File Path](https://leetcode.com/problems/longest-absolute-file-path/) | [C++](./algorithms/cpp/longestAbsoluteFilePath/LongestAbsoluteFilePath.cpp)|Medium|
 |387|[First Unique Character in a String](https://leetcode.com/problems/first-unique-character-in-a-string/) | [C++](./algorithms/cpp/firstUniqueCharacterInAString/FirstUniqueCharacterInAString.cpp)|Easy|
diff --git a/algorithms/cpp/eliminationGame/EliminationGame.cpp b/algorithms/cpp/eliminationGame/EliminationGame.cpp
@@ -0,0 +1,41 @@
+// Source : https://leetcode.com/contest/2/problems/elimination-game/
+// Author : Hao Chen
+// Date   : 2016-09-07-
+
+/********************************************************************************** 
+ * 
+ * There is a list of sorted integers from 1 to n. Starting from left to right, remove the first number and every other 
+ * number afterward until you reach the end of the list.
+ * 
+ * Repeat the previous step again, but this time from right to left, remove the right most number and every other number 
+ * from the remaining numbers.
+ * 
+ * We keep repeating the steps again, alternating left to right and right to left, until a single number remains.
+ * 
+ * Find the last number that remains starting with a list of length n.
+ * 
+ * Example:
+ * 
+ * Input:
+ * n = 9,
+ * 1 2 3 4 5 6 7 8 9
+ * 2 4 6 8
+ * 2 6
+ * 6
+ * 
+ * Output:
+ * 6
+**********************************************************************************/
+
+class Solution {
+public:
+    int lastRemaining(int n) {
+        int start = 1, step = 1;
+        while (n > 1) {
+            start += step + (n-2)/2 * 2*step;
+            n /= 2;
+            step *= -2;
+        }
+        return start;
+    }
+};
