O(n) solution to Multiply Others problem in F#

Anoth­er tasty chal­lenge that I ran into dur­ing my prepa­ra­tion for tech­ni­cal inter­views is this seem­ing­ly sim­ple prob­lem from Face­book.

input [2,3,1,4]
out­put [12,8,24,6]

Mul­ti­ply all fields except it’s own posi­tion.

1. no use of divi­sion
2. com­plex­i­ty in O(n)

The main chal­lenge is in mak­ing the algo­rithm run in O(n) time.

One solu­tion I saw (and thought it was quite clever) is to main­tain two tem­po­rary arrays, cal­cu­lat­ed by mul­ti­ply­ing the ele­ments of the input array from front-to-back, and back-to-front.

ie. input is [ 2, 3, 1, 4 ]

The front array starts with [ 1, 0, 0, 0 ], and start­ing from posi­tion 1, we can say front[i] = front[i-1] * input[i-1] and end up with [ 1, 2, 6, 6 ] (which is the prod­uct of all the input ele­ments before that posi­tion.

The rear array starts with [ 0, 0, 0, 1 ] and start­ing from posi­tion 2 (ie, sec­ond to last), we can say rear[i] = rear[i+1] * input[i+1] and end up with [ 12, 4, 4, 1 ].

And final­ly we can work out the out­put array by mul­ti­ply­ing the cor­re­spond­ing ele­ments in the front and rear arrays, and that runs in O(n) of time and space.

Here’s the imple­men­ta­tion in F#.


Try it Yourself