add 989

fishercoder1534 · fishercoder1534 · commit 4822218983a7 · 2019-02-15T09:35:25.000-08:00
diff --git a/README.md b/README.md
@@ -29,6 +29,7 @@ Your ideas/fixes/algorithms are more than welcome!
 
 |  #  |      Title     |   Solutions   | Time          | Space         | Video  | Difficulty  | Tag                   
 |-----|----------------|---------------|---------------|---------------|--------|-------------|-------------
+|989|[Add to Array-Form of Integer](https://leetcode.com/problems/add-to-array-form-of-integer/)|[Solution](../master/src/main/java/com/fishercoder/solutions/_989.java) | O(max(N, logk)) | O(max(N, logk)) | |Easy| Array
 |985|[Sum of Even Numbers After Queries](https://leetcode.com/problems/sum-of-even-numbers-after-queries/)|[Solution](../master/src/main/java/com/fishercoder/solutions/_985.java) | O(n) | O(n) | |Easy| Array
 |977|[Squares of a Sorted Array](https://leetcode.com/problems/squares-of-a-sorted-array/)|[Solution](../master/src/main/java/com/fishercoder/solutions/_977.java) | O(nlogn) | O(1) | |Easy| Array
 |976|[Largest Perimeter Triangle](https://leetcode.com/problems/largest-perimeter-triangle/)|[Solution](../master/src/main/java/com/fishercoder/solutions/_976.java) | O(nlogn) | O(1) | |Easy| Math Array 
diff --git a/src/main/java/com/fishercoder/solutions/_989.java b/src/main/java/com/fishercoder/solutions/_989.java
@@ -0,0 +1,80 @@
+package com.fishercoder.solutions;
+
+import java.util.ArrayList;
+import java.util.Collections;
+import java.util.List;
+
+/**
+ * 989. Add to Array-Form of Integer
+ *
+ * For a non-negative integer X, the array-form of X is an array of its digits in left to right order.  For example, if X = 1231, then the array form is [1,2,3,1].
+ *
+ * Given the array-form A of a non-negative integer X, return the array-form of the integer X+K.
+ *
+ * Example 1:
+ *
+ * Input: A = [1,2,0,0], K = 34
+ * Output: [1,2,3,4]
+ * Explanation: 1200 + 34 = 1234
+ * Example 2:
+ *
+ * Input: A = [2,7,4], K = 181
+ * Output: [4,5,5]
+ * Explanation: 274 + 181 = 455
+ * Example 3:
+ *
+ * Input: A = [2,1,5], K = 806
+ * Output: [1,0,2,1]
+ * Explanation: 215 + 806 = 1021
+ * Example 4:
+ *
+ * Input: A = [9,9,9,9,9,9,9,9,9,9], K = 1
+ * Output: [1,0,0,0,0,0,0,0,0,0,0]
+ * Explanation: 9999999999 + 1 = 10000000000
+ *
+ * Note：
+ *
+ * 1 <= A.length <= 10000
+ * 0 <= A[i] <= 9
+ * 0 <= K <= 10000
+ * If A.length > 1, then A[0] != 0
+ */
+public class _989 {
+  public static class Solution1 {
+    public List<Integer> addToArrayForm(int[] A, int K) {
+      List<Integer> kDigitsReversed = new ArrayList<>();
+      int divisor = 10;
+      while (K != 0) {
+        kDigitsReversed.add(K % divisor);
+        K /= 10;
+      }
+      List<Integer> result = new ArrayList<>();
+      int prevFlow = 0;
+      for (int i = A.length - 1, j = 0; i >= 0 || j < kDigitsReversed.size(); i --, j++) {
+        int sum;
+        if (i >= 0 && j < kDigitsReversed.size()) {
+          sum = A[i] + kDigitsReversed.get(j);
+        } else if (i >= 0) {
+          sum = A[i];
+        } else {
+          sum = kDigitsReversed.get(j);
+        }
+        int flow = 0;
+        if (prevFlow != 0) {
+          sum += prevFlow;
+        }
+        if (sum > 9) {
+          flow = 1;
+        }
+        sum %= 10;
+        prevFlow = flow;
+        result.add(sum);
+      }
+      if (prevFlow != 0) {
+        result.add(prevFlow);
+      }
+      Collections.reverse(result);
+      return result;
+    }
+  }
+}
diff --git a/src/test/java/com/fishercoder/_989Test.java b/src/test/java/com/fishercoder/_989Test.java
@@ -0,0 +1,42 @@
+package com.fishercoder;
+
+import com.fishercoder.solutions._989;
+import java.util.Arrays;
+import org.junit.BeforeClass;
+import org.junit.Test;
+
+import static junit.framework.Assert.assertEquals;
+
+public class _989Test {
+  private static _989.Solution1 solution1;
+  private static int[] A;
+
+  @BeforeClass
+  public static void setup() {
+    solution1 = new _989.Solution1();
+  }
+
+  @Test
+  public void test1() {
+    A = new int[] {1, 2, 0, 0};
+    assertEquals(Arrays.asList(1, 2, 3, 4), solution1.addToArrayForm(A, 34));
+  }
+
+  @Test
+  public void test2() {
+    A = new int[] {2, 7, 4};
+    assertEquals(Arrays.asList(4, 5, 5), solution1.addToArrayForm(A, 181));
+  }
+
+  @Test
+  public void test3() {
+    A = new int[] {2, 1, 5};
+    assertEquals(Arrays.asList(1, 0, 2, 1), solution1.addToArrayForm(A, 806));
+  }
+
+  @Test
+  public void test4() {
+    A = new int[] {9, 9, 9, 9, 9, 9, 9, 9, 9, 9};
+    assertEquals(Arrays.asList(1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0), solution1.addToArrayForm(A, 1));
+  }
+}
