Add to Array-Form of Integer, Lists Manipulation
Problem: https://leetcode.com/problems/add-to-array-form-of-integer/description/
Key is to use list manipulations in your preferred language, in my case, C#. Below, thx, ACC.
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 <= 100000 <= A[i] <= 90 <= K <= 10000- If
A.length > 1, thenA[0] != 0
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;
}
}
I have decided to merge all checks into a single loop:
ReplyDeleteclass 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 :)