Another tasty challenge that I ran into during my preparation for technical interviews is this seemingly simple problem from Facebook.

*input [2,3,1,4] *

*output [12,8,24,6] *

*Multiply all fields except it’s own position. *

*Restrictions: *

*1. no use of division *

*2. complexity in O(n)*

The main challenge is in making the algorithm run in O(n) time.

One solution I saw (and thought it was quite clever) is to maintain two temporary arrays, calculated by multiplying the elements 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 starting from position 1, we can say **front[i] = front[i-1] * input[i-1]** and end up with [ 1, 2, 6, 6 ] (which is the product of all the input elements before that position.

The **rear** array starts with [ 0, 0, 0, 1 ] and starting from position 2 (ie, second to last), we can say **rear[i] = rear[i+1] * input[i+1]** and end up with [ 12, 4, 4, 1 ].

And finally we can work out the output array by multiplying the corresponding elements in the **front** and **rear** arrays, and that runs in O(n) of time and space.

Here’s the implementation in F#.

## Try it Yourself

## Links

:)

let multOthers : int list -> int list =

fun xs ->

let rec hlp n = function

| [ ] | [_] -> [ ] | x :: xs -> let i = x*n in i :: (hlp i xs)

(1 :: xs |> hlp 1,

1 :: xs |> List.rev |> hlp 1 |> List.rev)

||> List.zip

|> List.map(fun (x,y) -> x*y)

[ 2; 3; 1; 4; ] |> multOthers

(it probably doesn’t look nice cos of no monospace font)

yeah, you’re right, the font makes it hard to read, can you try editing it and put them inside a code block? see here

let multOthers : int list -> int list =

fun xs ->

let rec hlp n = function

| [ ] | [_] -> [ ] | x :: xs -> let i = x*n in i :: (hlp i xs)

(1 :: xs |> hlp 1,

1 :: xs |> List.rev |> hlp 1 |> List.rev)

||> List.zip

|> List.map(fun (x,y) -> x*y)

[ 2; 3; 1; 4; ] |> multOthers

Much better :)

mm.. getting the wrong result – [24; 24; 24; 24]

Yeah, my bad, forgot the ()

...

(1 :: xs |> hlp 1,

1 :: (xs |> List.rev) |> hlp 1 |> List.rev)

...

Yeah, my bad, forgot ()

...

(1 :: xs |> hlp 1,

1 :: (xs |> List.rev) |> hlp 1 |> List.rev)

...

Hi Yan. Your site brings my browser to a crashing halt with all of the ads. By disabling Flash, I was able to make the page stable enough to leave this comment, but it’s still using loads of CPU. I believe it’s pretty much unusable on mobile for this reason. Would you consider removing some ads and/or widgets?

Here’s one using effectively the same algorithm but with more standard library functions and no mutation:

let multiplyOthers xs =

let front = Array.scan (*) 1 xs

let back = Array.scanBack (*) xs 1

Array.map2 (*) front.[..front.Length - 2] back.[1..]

Pingback: Equilibrium Index problem in F# | theburningmonk.com