DSA Series: Add to Array-Form of Integer

Not quite long, I decided I was going to get back to solving DSA problems to get better at problem solving and also improve my writing skills because I will be taking time to write the back story of how I solved each problem. Fast forward to this morning, I started with a lot more than I could chew (it was a medium-ranked problem 😄). Somehow I found my way to “Add to Array-Form of Integer” through the similar questions options thinking this would be simple. 



The question:
The array-form of an integer num is an array representing its digits in left-to-right order.

• For example, for num = 1321, the array form is [1,3,2,1]. Given num, the array-form of an integer, and an integer k, return the array-form of the integer num + k. 
e.g. 
Example 1:

Input: num = [1,2,0,0], k = 34
Output: [1,2,3,4]
Explanation: 1200 + 34 = 1234

My First Approach:
I looked at it briefly and concluded that I would convert num to a string then add it to k. Sounds good right? ✌️

Let me show you the implementation:

function addToArrayForm(num: number[], k: number): number[] {
    const wholeNumber = Number(num.join(''));
    const sum = wholeNumber + k
    const array = Array.from(String(sum), Number)
    return array;
};

The test case passed and I reassured myself that the problem was a slice of cake so I decided to submit my solution only to see I only passed 90/152 test cases….
Then I saw this particular failing test:

Input: num = [1,2,6,3,0,7,1,7,1,9,7,5,6,6,4,4,0,0,6,3], k = 516 

My Output  = [1,2,6,3,0,7,1,7,1,9,7,5,6,6,4,4,0,0,0,0]
Expected Output = [1,2,6,3,0,7,1,7,1,9,7,5,6,6,4,4,0,5,7,9]

I couldn’t fathom why I had four trailing zeros; this led me to research on Google to find out what the issue was: 


I discovered I had run into an issue because my number had exceeded the Maximum Safe Integer Limit in JavaScript.

In JavaScript, all standard numbers are stored as 64-bit floating-point values (doubles).

JavaScript can only precisely handle 9, 007, 199, 254, 740, 991. If you are interested in pronouncing that value, it is: Nine quadrillion seven trillion one hundred ninety-nine billion two hundred fifty-four million seven hundred forty thousand nine hundred ninety-one. - Don’t mention!

My array has 20 digits, producing a value of 12,630,717,197,566,440,063, which is higher than the Maximum Safe Integer value. So, when a number gets this big, JavaScript loses precision and rounds the last few digits to zero. Hence the reason I had trailing zeros. After my research, I discovered the solution to my problem was to use BigInt() instead of Number() because it can handle integers of practically any size without losing precision.


Using BigInt() adds a n suffix to a number to signify that it is a BigInt data type, not a normal number e.g 12630717197566440063n. My thought process was to use BigInt() then convert my response to type Number to eliminate the n and add the other value. This will only result in the trailing zero issue.

I wanted to turn the BigInt value to type Number so that I could add the other variable that was passed to the function, but adding a BigInt and Number value throws a TypeError.



Since I was clear with possible pitfalls I needed to avoid, I took this approach:


1. I created a variable wholeNumber to join the array of numbers and most importantly wrap a BigInt() around it.

2. I created a variable sum to allow me to add wholeNumber(type BigInt) to the second variable wrapped in BigInt in-built object to make both values of the same data type.
Don’t forget, I need to return the answer in an array form. 

3. I created a variable array with the intention of getting the final answer that returns the new array instance. I decided to go for the Array.from() built-in static method so that I can convert a number into an array of its individual numerical digits. Within the method I passed two arguments String(sum) to converts the BigInt sum value to String and the Number type as the map function that converts each elements of the array into a number



You can read more about Array.from() here. 



Here is my solution that passed all the submission test cases:

function addToArrayForm(num: number[], k: number): number[] {
    const wholeNumber = BigInt(num.join(''));
    const sum = wholeNumber + BigInt(k);
    const array = Array.from(String(sum), Number);
    return array;
};

The initial failing example now passed:

Input: num = [1,2,6,3,0,7,1,7,1,9,7,5,6,6,4,4,0,0,6,3], k = 516 

My Output  = [1,2,6,3,0,7,1,7,1,9,7,5,6,6,4,4,0,5,7,9]
Expected Output = [1,2,6,3,0,7,1,7,1,9,7,5,6,6,4,4,0,5,7,9]

Although my submission was accepted, it wasn’t optimised in terms of runtime and memory. My solution has a runtime of 16ms while the most optimised solution has a runtime of 0ms. In subsequent series, I will pay attention to optimisation and also add it to the documentation.

This was from Leetcode. You can check it out here.



Thank you for reading and see you on the next one!