Got it. You mean use the formula for summing an arithmetic progression twice and take account of duplicates.
Sheer genius! On Sat, May 7, 2011 at 11:56 AM, Eugene Kirpichov <ekirpic...@gmail.com> wrote: > 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/ > -- -- Regards, KC _______________________________________________ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe