leetcode

commit d3a2c8adeac5d624ec69f230fadaaf31c74fe6a8
parent 8ba924436554cbda833edd926627269b7d3b3fcc
Author: AndrewLockVI <andrewlaack1@gmail.com>
Date:   Tue,  2 May 2023 19:26:14 -0500

Completed elimination game problem

Diffstat:
A
elimination-game/elimination-game.dart
 | 
27
+++++++++++++++++++++++++++

1 file changed, 27 insertions(+), 0 deletions(-)
diff --git a/elimination-game/elimination-game.dart b/elimination-game/elimination-game.dart
@@ -0,0 +1,27 @@
+//Starting from the first index remove every other element. Then
+//sweep back the other way from right to left until there is only
+//one value remaining. Return the remaining value. 
+//The time complexity of this code is O(n^2) where n is the length of the list
+//it is this slow because the a memcopy is required to remove a specific index from a list (O(n) time)
+//This code is too slow for leet code, but it is the intuitive solution to the problem.
+
+class Solution {
+  int lastRemaining(int n) {
+    List<int> vals = [];
+    for(int i = 1 ; i <= n ; ++i){
+      vals.add(i);
+    }
+    while(vals.length > 1){
+      for(int i = 0 ; i < vals.length ; i += 1){
+        vals.removeAt(i);
+      }
+      if(vals.length == 1){
+        break;
+      }
+      for(int i = vals.length - 1 ; i >= 0; i -= 2){
+        vals.removeAt(i);
+      }
+    }
+    return vals[0];
+  }
+}