Add to Array-Form of Integer, Lists Manipulation

-
Problem: https://leetcode.com/problems/add-to-array-form-of-integer/description/

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. 1 <= A.length <= 10000
    2. 0 <= A[i] <= 9
    3. 0 <= K <= 10000
    4. If A.length > 1, then A[0] != 0
    Key is to use list manipulations in your preferred language, in my case, C#. Below, thx, ACC.


    public class Solution
{
 public IList AddToArrayForm(int[] A, int K)
 {
  LinkedList retVal = new LinkedList();
  foreach (int a in A) retVal.AddFirst(a);

  LinkedListNode node = retVal.First;
  int carryOver = 0;
  while (node != null && K > 0)
  {
   int temp = node.Value;
   node.Value = (temp + K % 10 + carryOver) % 10;
   carryOver = (temp + K % 10 + carryOver) / 10;
   node = node.Next;
   K /= 10;
  }
  while (node != null)
  {
   int temp = node.Value;
   node.Value = (temp + carryOver) % 10;
   carryOver = (temp + carryOver) / 10;
   node = node.Next;
  }
  while (K > 0)
  {
   retVal.AddLast((K % 10 + carryOver) % 10);
   carryOver = (K % 10 + carryOver) / 10;
   K /= 10;
  }
  if (carryOver > 0)
  {
   retVal.AddLast(carryOver);
  }

  List list = new List();
  for (LinkedListNode n = retVal.Last; n != null; n = n.Previous)
  {
   list.Add(n.Value);
  }

  return list;
 }
}

    Comments

    1. TarasFebruary 14, 2019 at 11:31 PM

      I have decided to merge all checks into a single loop:

      class Solution:
      def addToArrayForm(self, A: 'List[int]', K: int) -> 'List[int]':
      carry, idx, result = 0, len(A) - 1, []
      while K > 0 or idx >= 0 or carry:
      old_digit, idx = A[idx] if idx >= 0 else 0, idx - 1
      sum, K = old_digit + (K % 10) + carry, K // 10
      carry = sum // 10
      result.append(sum % 10)

      return list(reversed(result))

      https://gist.github.com/ttsugriy/dad95e836845bdb22ee44358b115f2e4

      In general pointer based data structures like linked list are extremely inefficient even for everything but making lots of removals/additions in the middle of the collection because they are very cache-unfriendly. Double linked list is also using a lot of memory which explains why the memory footprint is 25.8MB (for comparison the Python implementation above is using 12.7MB). If I weren't so lazy I would preallocate an array of the size of A + 1 and use it instead of using dynamically sized DS like vector/ArrayList :)

      ReplyDelete

    Post a Comment

    Popular posts from this blog

    Count Binary Substrings

    -
    Image
    Problem by Leetcode:  https://leetcode.com/problems/count-binary-substrings/description/ Give a string  s , count the number of non-empty (contiguous) substrings that have the same number of 0's and 1's, and all the 0's and all the 1's in these substrings are grouped consecutively. Substrings that occur multiple times are counted the number of times they occur. Example 1: Input: "00110011" Output: 6 Explanation: There are 6 substrings that have equal number of consecutive 1's and 0's: "0011", "01", "1100", "10", "0011", and "01". Notice that some of these substrings repeat and are counted the number of times they occur. Also, "00110011" is not a valid substring because all the 0's (and 1's) are not grouped together. Example 2: Input: "10101" Output: 4 Explanation: There are 4 substrings: "10", "01", "10", "01&
    Read more

    Count Vowels Permutation: Standard DP

    -
    Image
    Standard DP problem:  https://leetcode.com/problems/count-vowels-permutation/ Given an integer  n , your task is to count how many strings of length  n  can be formed under the following rules: Each character is a lower case vowel ( 'a' ,  'e' ,  'i' ,  'o' ,  'u' ) Each vowel  'a'  may only be followed by an  'e' . Each vowel  'e'  may only be followed by an  'a'  or an  'i' . Each vowel  'i'   may not  be followed by another  'i' . Each vowel  'o'  may only be followed by an  'i'  or a  'u' . Each vowel  'u'  may only be followed by an  'a'. Since the answer may be too large, return it modulo  10^9 + 7. Example 1: Input: n = 1 Output: 5 Explanation: All possible strings are: "a", "e", "i" , "o" and "u". Example 2: Input: n = 2 Output: 10 Explanation: All possible strings are
    Read more

    Maximum Number of Balloons

    -
    Image
    #431 in my solved list:  https://leetcode.com/problems/maximum-number-of-balloons/ Given a string  text , you want to use the characters of  text  to form as many instances of the word  "balloon"  as possible. You can use each character in  text   at most once . Return the maximum number of instances that can be formed.   Example 1: Input: text = "nlaebolko" Output: 1 Example 2: Input: text = "loonbalxballpoon" Output: 2 Example 3: Input: text = "leetcode" Output: 0 Constraints: 1 <= text.length <= 10^4 text  consists of lower case English letters only. Solution is as follows:  - Count the number of occurrences of the "balloon" letters in the input string  - For "l" and "o", divide the count by 2  - If the balloon string is not fully covered, return 0  - Return the min number across all occurrences Code is below, cheers, ACC. public class Solution {     public int M
    Read more