One doesn't have to touch them to compute their sum. 2011/5/7 KC <kc1...@gmail.com>: > 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 >
-- Eugene Kirpichov Principal Engineer, Mirantis Inc. http://www.mirantis.com/ Editor, http://fprog.ru/ _______________________________________________ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
