productExceptSelf.js

You have an array nums. We determine two functions to perform on nums. In both cases, n is the length of nums:
fi(nums) = nums[0] · nums[1] · ... · nums[i - 1] · nums[i + 1] · ... · nums[n - 1]. (In other words, fi(nums) is the product of all array elements except the ithf.)
g(nums) = f0(nums) + f1(nums) + ... + fn-1(nums).
Using these two functions, calculate all values of f modulo the given m. Take these new values and add them together to get g. You should return the value of g modulo the given m.

Last weekend I attend the Powerful Transitions for an Epic Future talk. It was great to go out and listen to the speakers; I enjoyed a quiet weekend morning on my own to reflect on my priorities. It was rejuvenating! I’m still wondering what exactly my transition is but this is the big question I’m chewing on right now: What would you do if you weren’t afraid?

Part of the answer is — I will write code and then talk about it with friends, family, strangers, whoever will participate!

I started this challenge a few weeks ago. It’s simple enough, on first glance, so I wrote down some notes (to get in the habit of white-boarding) and then started writing the code.

https://commons.wikimedia.org/wiki/File:Poser-une-multiplication.gif

With my first draft, I got half the tests to pass — “I’m on the right path!” I trace through and fiddle with it a little, I check the inputs for the tests that fail. Ooooh… those are all really, really large numbers. Oh crud, I have to write BigInt — JavaScript can’t handle integers greater than 2⁵³ and this challenge needs precision!

It took a few days here and there to draw out the solution, code it, and debug BigMultiply but I finally got it. Nothing fancy:

function bigMultiply(a, b) {
//doesn't handle signs
    if(a.length < 10) {
return (parseInt(a) * parseInt(b)).toString();
}
    var product = [];
    for(var x = a.length - 1; x >= 0; x--) {
var carry = 0;
       for(var y = b.length - 1; y >= 0; y--) {
if(typeof(product[x+y]) == "undefined"){ product[x+y] = 0; }
          var t = product[x+y] + carry + (parseInt(a[x]) * parseInt(b[y]));
            product[x+y] = t % 10;
carry = Math.floor(t/10);
}
       if(carry > 0) {
if (x == 0){
product.unshift(carry);
} else {
product[x-1] = carry;
}
}
}
    return product.join("");
}

And then I realized that I also needed to divide those big numbers! That one took longer, it’s much simpler but I kept working on it while I was tired (will I ever learn not to do that?!) and I dug the hole too deep… So, I started over with a blank note card and a colorful pen.

https://en.wikipedia.org/wiki/Long_division
function bigDivide(a, b){
//assumes b is not a big number
//no decimals; integers only
//doesn't handle signs
//assumes remainder is not a big number
    // a / b
    if(a.length < 25) {
var q = Math.floor(parseInt(a) / parseInt(b));
var r = parseInt(a) - (q * parseInt(b));
return {result: q.toString(), remainder: r};
}
    var result = [];
var remainder = 0;
    var d = a.substring(0, 1);
a = a.substr(1);
    do {
var c = Math.floor(parseInt(d) / parseInt(b));
var q = c * parseInt(b);
remainder = d - q;
result.push(c);
        if(a.length == 0) { 
break;
}
        d = remainder.toString() + a.substring(0, 1);
a = a.substr(1);
    }while(a.length >= 0);
    result = result.join("");
if(result.length > 1){
while(result.startsWith("0") && result.length > 1){
result = result.substr(1);
}
}
   return {result: result, remainder: remainder};
}

Little did I know… I was still in for a surprise — the multiplication takes ages when there‘s a very large nums array given. I learned about Karatsuba and there might be some other algorithms but I’ve been working on this (and procrastinating a bit!) for long enough so, putting it on a shelf as I shake my fist at this one’s onion peel difficulty! It was certainly fun to work on but I would expect that being able to identify these cases (but not necessarily solve them!) is acceptable for interviewers.