An Interesting Little Problem * OJ's rants - The Diigo Meta page

• 17 May 10
  

  James Choate

  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.

  Programming Algorithm

• 02 Aug 08
  

  Sam Kitonyi

  haskell functional programming python algorithms

  • 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). 
  • -- 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 desp problem input = zipWith (*) front back where  front = init (scanl (*) 1 input)  back = tail (scanr (*) 1 input)
  • A = [4,3,2,1,2] output = [] result = 1 for n in A:  output.append(result)  result *= n result = 1 for i, n in reversed(list(enumerate(A))):  output[i] *= result  result *= n print output
  • main = do putStrLn $ show products_of_peers  where (_, products_of_peers) = multiply_peers 1 [4, 3, 2, 1, 2]  where multiply_peers _ [] = (1, [])  multiply_peers l (x:xs) = (r * x, l * r : ps)  where (r, ps) = multiply_peers (l * x) xs

  3 more annotations...

Would you like to comment?

Join Diigo for a free account, or sign in if you are already a member.