This post was inspired by a recent interview question that was posted over at fsharp.it. It’s one of those neat little questions which looks really simple on the surface but is quite tricky.

The question apparently originates from an interview that someone had with Google, and goes something like this:

There is an array A[N] of N integers. You have to compose an array Output[N] such that Output[i] will be equal to the product of all the elements of A[] except A[i].

Example:     INPUT:[4, 3, 2, 1, 2]     OUTPUT:[12, 16, 24, 48, 24]

Note: Solve it without the division operator and in O(n).

I’ll cut to the chase, here’s the source to my solution:

1
2
3
4
5
6
7
8
9

vals :: [Int]
vals = [ 4, 3, 2, 1, 2 ]

answers :: [Int]
answers = [ front !! (x-1) * back !! (x+1) | x <- [1..length vals] ]
  where
    front = scanl1 (*) temp
    back = scanr1 (*) temp
    temp = [1] ++ vals ++ [1]

I’m hoping that this is quite self-explanatory. But in case it’s not, I’ll cover some of the gory bits.

The core of the problem is coming up with a way of determining the value of the product of numbers from the start of the list up to a given index, and to do the same at the other end of the list from that given index.

I thought that the easiest way would be to create two lists: both of them containing the compounded products of the numbers in the list, but each of them in different directions. To generate those lists, I thought that I’d add the value of 1 to the list, both at the start and at the end, as it would allow me to do two things:

1. Generate the lists using the scanl1 and scanr1 functions.
2. Index into the list using a counter that’s based on the size of the original values without having to worry about going past the bounds of the list.

Here’s the output when I execute answers in GHCi:

Prelude> :l google.hs
[1 of 1] Compiling Main             ( google.hs, interpreted )
Ok, modules loaded: Main.
*Main> answers
[12,16,24,48,24]
*Main>

Problem solved in O(n). Neato! After feeling rather chuffed with myself I thought I’d go back to Fsharp.it and check out the answer posted there. The principle was similar, but the implementation listed was a little longer.

So I thought I’d have a go at writing up my solution using F#. It didn’t seem like a stretch until I realised how little of the language I know (I’m currently reading through Expert F#, but I’m still far from being one myself). Here’s what I came up with:

1
2
3
4
5
6
7
8
9
10
11
12

#light

let vals = [ 4; 3; 2; 1; 2; ]

let mul a b = a * b
let (++) = List.append

let answers =
  let temp = [1] ++ vals ++ [1]
  let front = List.scan1_left mul temp |> List.to_array
  let back = List.scan1_right mul temp |> List.to_array
  seq { for x in [1 .. vals.Length] -> front.[x-1] * back.[x+1] }

A few things you might notice:

1. My syntax highlighter plugin doesn’t currently support F# :)
2. I use a similar method to the Haskell solution, but ended up having to convert the front and back lists to arrays. The reason was because I need to be able to index into the resulting integer set, and I can’t do that with lists (if I’m wrong, please let me know!)
3. I defined a function called mul which does a simple multiplication. I wanted to pass () as the first parameter to the scan1_ functions, but the interpreter took that as the start of a comment instead! So I had to resort to a dodgey hack. If you know a way around this, please let me know.
4. I wrote my own (++) operator because I didn’t want to have to write List.append more than once :)

I did enjoy having a dabble with F# for the first time in ages, though I have to admit I much prefer using VIM and fsi.exe instead of Visual Studio and the interactive F# add-in.

As always, feedback and criticism welcomed (and needed).

Update

After some great feedback (see below), I’ve come to realise that the !! operator in Haskell is actually O(n) itself. Hence it was a bad choice for inclusion. Back to the drawing board for me!

Here are a couple of submitted Haskell solutions.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

-- by lf
scanm f z xs = zipWith f (scanl f z xs) (tail $ scanr f z xs)
main = print $ scanm (*) 1 [4,3,2,1,2]

-- by Henning
answers :: [Int] -> [Int]
answers vals = zipWith (*) front (drop 1 back)
  where
  front = scanl (*) 1 vals
  back = scanr (*) 1 vals

-- by desp
problem input = zipWith (*) front back where
  front = init (scanl (*) 1 input)
  back = tail (scanr (*) 1 input)

-- by foobar
foo [] _ = ([], 1)
foo (x:xs) acc = let (l, m) = foo xs (acc*x)
                 in ((m*acc):l , m*x)

Thanks for the submissions guys :) Sorry for not including the imperative versions in the update.