leetcode

commit 62f068260943f5547017f01f2f9c1cf849a83559
parent baeedb13864ae7475d7e76aeeea6dccfa8806ef8
Author: AndrewLockVI <andrewlaack1@gmail.com>
Date:   Wed, 19 Apr 2023 10:36:21 -0500

Completed add binary with dart

Diffstat:
A
add-binary/add-binary.dart
 | 
64
++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++

1 file changed, 64 insertions(+), 0 deletions(-)
diff --git a/add-binary/add-binary.dart b/add-binary/add-binary.dart
@@ -0,0 +1,64 @@
+//Add two strings together that are "binary" strings
+//with ones and zeroes. I did this by assigning them to a reversed
+//list and then going through them one value at a time carrying the remainders.
+//I another approach is to use binary to decimal conversion, but
+//the problem is that in leetcode it says b.length<=10^4 which means
+//the input could be larger than 64 bits thus can't be stored in an int.
+//The worst case time complexity of this is O(n^2).
+//Runtime: 270ms Beats: 84.31%
+//Memory: 142.5MB Beats: 74.51%
+
+void main(){
+    Solution sol = new Solution();
+    print(sol.addBinary("010110101011", "1010111010101");
+
+}
+
+class Solution {
+
+String addBinary(String a, String b) {
+    List<String> long;
+    List<String> short;
+    if(a.length > b.length){
+        long = a.split("");
+        short = b.split("");
+    }
+    else{
+        long = b.split("");
+        short = a.split("");
+    }
+    short = short.reversed.toList();
+    long = long.reversed.toList();
+    for(int i = 0 ; i < short.length ; ++i){
+        int carry = 0;
+        if(short[i] == '0'){
+            continue;
+        }
+        if(long[i] == '1'){
+            long[i] = '0';
+            carry = 1;
+        }
+        else{
+            long[i] = '1';
+            continue;
+        }
+        int next_val = i + 1;
+        while(carry != 0){
+            if(next_val >= long.length){
+                long.add('0');
+                continue;
+            }
+            if(long[next_val] == '1'){
+                long[next_val] = '0';
+            }
+            else{
+                long[next_val] = '1';
+                carry = 0;
+            }
+            next_val += 1;
+
+        }
+    }
+    return long.reversed.join('');
+  }
+}