programmer thoughts

Earlier today I was busy working on testing a tooltip mechanism by hiding the initial and dismissal delays behind Executors, when a coworker begins talking about an interesting programming question that appeared on a blog this weekend.

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

The solution using division becomes readily apparent, but doesn't solve the problem.  Thinking about it for a few minutes the need to store all the products to the left and right of the element becomes apparent.  I begin to wonder if lazy evaluation can help with this problem.   Eventually I decided not, but this is what I came up with:

f = map (uncurry (*)) . pair 1
 
pair left (x:xs) = (left,right):rest
    where rest = pair (left*x) xs
          right = if rest == [] then 1 else (head xs) * (snd (head rest))
pair y [] = []
 
test = f [1,2,3,4] == [24,12,8,6]

I was too blinded by thinking how neat it was to build the left portion moving right down the list, and building the right portion by carrying values back to the left, thus using only one pass, that I completely missed the much more readable scanl/scanr based solutions presented in the update.