package com.fishercoder.solutions;

import java.util.ArrayList;
import java.util.List;

/**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

 */
public class _390 {
    
    //then I turned to Discuss and found this post: https://discuss.leetcode.com/topic/55870/share-my-solutions-for-contest-2
    //instead of literally removing half of the elements in each scan, this solution is just moving the pointer to point to next start position
    //So brilliant!
    public int lastRemaining(int n) {
        int remaining = n;
        int start = 1;
        int step = 2;
        boolean forward = true;
        while (remaining > 1) {
            remaining /= 2;
            if (forward) {
                start = start + step * remaining - step / 2;
            } else {
                start = start - step * remaining + step / 2;
            }
            step *= 2;
            forward = !forward;
        }
        return start;
    }

    //I tried brute force, all producing the correct output, but got TLE by OJ.
    public static int lastRemaining_brute_force_TLE(int n) {
        List<Integer> list = new ArrayList();
        for (int i = 0; i < n; i++) {
            list.add(i + 1);
        }
        boolean forward = true;
        while (list.size() > 1) {
            int size = list.size() / 2;
            if (list.size() == 1) {
                return list.get(0);
            }
            if (forward) {
                if (list.size() == 1) {
                    return list.get(0);
                }
                for (int i = 0; i <= size && i < list.size(); i++) {
                    list.remove(i);
                }
                forward = false;
            } else {
                if (list.size() == 1) {
                    return list.get(0);
                }
                for (int i = list.size() - 1, count = 0; i >= 0 && count <= size; count++) {
                    list.remove(i);
                    i -= 2;
                }
                forward = true;
            }
        }
        return list.get(0);
    }

    public static void main(String... strings) {
        System.out.println(lastRemaining_brute_force_TLE(5204));
        System.out.println(lastRemaining_brute_force_TLE(5058));
//        System.out.println(lastRemaining(10));
//        System.out.println(lastRemaining(9));
//        System.out.println(lastRemaining(3));
    }

}

@@ -33,63 +33,43 @@
 s;%0A%0A
-import java.util.ArrayList;%0Aimport java.util.List;%0A%0A/**
+/**%0A * 390. Elimination Game%0A *%0A * 
 Ther
@@ -684,62 +684,73 @@
 0 %7B%0A
+%0A
     
-%0A    //then I turned to Discuss and found this pos
+public static class Solution1 %7B%0A        /**%0A         * credi
 t: h
@@ -821,23 +821,17 @@
 ontest-2
-%0A    //
+ 
 instead 
@@ -832,16 +832,27 @@
 stead of
+%0A         *
  literal
@@ -930,16 +930,27 @@
 ving the
+%0A         *
  pointer
@@ -981,23 +981,17 @@
 position
-%0A    //
+ 
 So brill
@@ -996,16 +996,32 @@
 lliant!%0A
+         */%0A    
     publ
@@ -1054,24 +1054,28 @@
 ) %7B%0A        
+    
 int remainin
@@ -1085,24 +1085,28 @@
  n;%0A        
+  
+  
 int start = 
@@ -1108,16 +1108,20 @@
 rt = 1;%0A
+    
         
@@ -1134,32 +1134,36 @@
 ep = 2;%0A        
+    
 boolean forward 
@@ -1174,24 +1174,28 @@
 ue;%0A        
+  
+  
 while (remai
@@ -1218,16 +1218,20 @@
         
+    
 remainin
@@ -1242,32 +1242,36 @@
  2;%0A            
+ 
+   
 if (forward) %7B%0A 
@@ -1277,32 +1277,36 @@
                 
+   
+ 
 start = start + 
@@ -1338,32 +1338,36 @@
  2;%0A            
+    
 %7D else %7B%0A       
@@ -1367,32 +1367,36 @@
                 
+ 
+   
 start = start - 
@@ -1437,69 +1437,8 @@
     
-   
-%7D%0A            step *= 2;%0A            forward = !forward;%0A 
     
@@ -1454,1096 +1454,103 @@
     
-return start;%0A
     
-%7D%0A%0A
     
-//I tried brute force, all producing the correct output, but got TLE by OJ.%0A    public static int lastRemaining_brute_force_TLE(int n) %7B%0A        List%3CInteger%3E list = new ArrayList();%0A        for (int i = 0; i %3C n; i++) %7B%0A            list.add(i + 1);%0A        %7D%0A        boolean forward = true;%0A        while (list.size() %3E 1) %7B%0A            int size = list.size() / 2;%0A            if (list.size() == 1) %7B%0A                return list.get(0);%0A            %7D%0A            if (forward) %7B%0A                if (list.size() == 1) %7B%0A                    return list.get(0);%0A                %7D%0A                for (int i = 0; i %3C= size && i %3C list.size(); i++) %7B%0A                    list.remove(i);%0A                %7D%0A                forward = false;%0A            %7D else %7B%0A                if (list.size() == 1) %7B%0A                    return list.get(0);%0A                %7D%0A                for (int i = list.size() - 1, count = 0; i %3E= 0 && count %3C= size; count++) %7B%0A                    list.remove(i);%0A                    i -= 2;%0A                %7D%0A                forward = true;%0A    
+step *= 2;%0A                forward = !forward;%0A            %7D%0A            return start;%0A
     
@@ -1563,378 +1563,8 @@
     
-  
-  %7D%0A        return list.get(0);%0A    %7D%0A%0A    public static void main(String... strings) %7B%0A        System.out.println(lastRemaining_brute_force_TLE(5204));%0A        System.out.println(lastRemaining_brute_force_TLE(5058));%0A//        System.out.println(lastRemaining(10));%0A//        System.out.println(lastRemaining(9));%0A//        System.out.println(lastRemaining(3));%0A    %7D%0A
+%7D
 %0A%7D%0A

refactor 390