Do you mean O(1) complexity? Don't you have to touch at least the multiples of 3 & 5 making it O(k) where is the number of multiples of 3 and the number of multiples of 5?
On Fri, May 6, 2011 at 10:10 PM, Lyndon Maydwell <maydw...@gmail.com> wrote: > If you're looking for efficiency, I believe you can actually do #1 in > constant time: > > > On Sat, May 7, 2011 at 7:31 AM, <cas...@istar.ca> wrote: >> -- Instead of this >> -- sumMultiples3or5 s = sum [x | x <- [3..s-1], x `mod` 3 == 0 || x `mod` 5 >> == 0] >> >> >> -- Isn't this faster >> >> sumMultiples3or5 s = sum ([x | x <- [3,6..s-1]] `merge` [x | x <- >> [5,10..s-1]]) >> >> merge xs [] = xs >> merge [] ys = ys >> merge txs@(x:xs) tys@(y:ys) >> | x < y = x : xs `merge` tys >> | x > y = y : txs `merge` ys >> | otherwise = x : xs `merge` ys >> >> >> >> _______________________________________________ >> Haskell-Cafe mailing list >> Haskell-Cafe@haskell.org >> http://www.haskell.org/mailman/listinfo/haskell-cafe >> > > _______________________________________________ > Haskell-Cafe mailing list > Haskell-Cafe@haskell.org > http://www.haskell.org/mailman/listinfo/haskell-cafe > -- -- Regards, KC _______________________________________________ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe