# 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`ith`

f.)

`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.

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.

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.