# [Haskell-cafe] For Project Euler #1 isn't it more efficient to generate just the numbers you need? <Spoiler>

Eugene Kirpichov ekirpichov at gmail.com
Sat May 7 20:56:09 CEST 2011

```One doesn't have to touch them to compute their sum.

2011/5/7 KC <kc1956 at 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 <maydwell at 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,  <caseyh at istar.ca> wrote:
>>> -- 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
>>>
>>>
>>>
>>> _______________________________________________
>>>
>>
>> _______________________________________________
>>
>
>
>
> --
> --
> Regards,
> KC
>
> _______________________________________________