Benjamin Van Nguyen

A place to hone our problem solving skills and enjoy eldritch art — and hopefully retain our sanity whilst doing so. I post a coding challenge every few days for us to solve together so subscribe at the very bottom of the page to receive email notifications :)

Hello World

Ahead of me; an object that gleamed whitely in the newly bestowed rays of the ascending moon. That it was merely a gigantic piece of stone, I soon assured myself; but I was conscious of a distinct impression that its contour and position were not altogether the work of Nature. A closer scrutiny filled me with sensations I cannot express; for despite its enormous magnitude, and its position in an abyss which had yawned at the bottom of the sea since the world was young, I perceived beyond a doubt that the strange object was a well-shaped monolith whose massive bulk had known the workmanship and perhaps the worship of living and thinking creatures.

And we are live!

Welcome to my blog where I post cool Lovecraftian images and go through one coding challenge a day. This blog is meant to help others hone their problem-solving skills in addition to allowing me to sharpen my own. How it works is: I'll post the problem here as well as a link to the original so you can try it on your own. Once you're down you can go below to comment, reply, upvote, and downvote one another, but most importantly you'll be able to share your own solutions. All languages are welcome! I'll mostly be doing my solutions in Python, but every now and then I'll sneak in some Javascript and maybe some other language I happen to be learning at the moment like Golang :) 

Without further ado lets take a look at our first problem which comes from Project Euler:

The problemLink to problem
 

If we list all the natural numbers below 10 that are multiples of 3 or 5, 
we get 3, 5, 6 and 9. The sum of these multiples is 23.

Find the sum of all the multiples of 3 or 5 below 1000.


Before reading on, open the terminal and try solving this problem on your own first. The answer to this problem is 233168.

The Solution:

Since we are interested in multiples of 3 and 5 we definitely want to make use of the mod (%) operator. Those of you new to programming may not be familiar with the mod operator so let me just give you a brief introduction on how it works:
 

Ex 1:
10 ÷ 4 = 2, remainder 2
10 % 4 = 2 

Ex 2:
16 ÷ 3 = 5, remainder 1
16 % 3 = 1

Ex 3:
20 ÷ 10 = 2, remainder 0
20 % 10 = 0


You guys see what's going on? For the first example the mod operator is basically saying 10 divided by 4, but return the remainder. 10 divided by 4 gives us a remainder of 2, hence 10 mod 4 is 2! In the third example, 10 is a multiple of 20, meaning there will be a remainer of 0 if we do 20 divided by 10, hence 20 % 10 is 0. 

Now what does this mean in the context of the problem? It means that if we a number (n) is a multiple of 3, we'd expect n % 3 to give us 0. So onto our first order of business. How do we find all multiples of 3 and 5 in Python? Here's how:

for i in range(1000): # loops through 0-999
    if i % 3 == 0 or i % 5 == 0:
        # What next?


Now here is where things get interesting because of how many ways we can go about finding the sum of all these numbers. Here's three:

# Method 1: Initializing an integer-variable then incrementing

result = 0
for i in range(1000): # loops through 0-999
    if i % 3 == 0 or i % 5 == 0:
        result += i

 

# Method 2: Initializing an empty list, appending, then calling the sum function

nums = []
for i in range(1000): # loops through 0-999
    if i % 3 == 0 or i % 5 == 0:
        nums.append(i)
sum(nums)

 

# Method 3: Calling the sum function on a list comprehension

sum([i for i in range(1000) if i % 3 == 0 or i % 5 == 0])


Now out of all these methods, the first would definitely be my go-to for a multiple reasons. 

  1. A single integer in this case takes up less memory than a list.
  2. It's very readable (compared to method 3)
  3. It's the fastest.

Qualitatively, how would one know that method 1 is the quickest? I'll let you guys sort that out; but if you don't believe me here is some quantitative data I obtained using Python's timeit module.
 

from timeit import Timer

def method_1():
    result = 0
    for i in range(1000): 
        if i % 3 == 0 or i % 5 == 0:
            result += 1
    return result

def method_2():
    nums = []
    for i in range(1000): 
        if i % 3 == 0 or i % 5 == 0:
            nums.append(i)
    return sum(nums)

def method_3():
    return sum([i for i in range(1000) if i % 3 == 0 or i % 5 == 0])

t1 = Timer("method_1", "from __main__ import method_1")
print(f"Method 1 {t1.timeit(number=1000)} milliseconds")
t2 = Timer("method_2", "from __main__ import method_2")
print(f"Method 2 {t2.timeit(number=1000)} milliseconds")
t3 = Timer("method_3", "from __main__ import method_3")
print(f"Method 3 {t3.timeit(number=1000)} milliseconds")

# Method 1 1.4564022421836853e-05 milliseconds
# Method 2 1.9157014321535826e-05 milliseconds
# Method 3 1.9569997675716877e-05 milliseconds

 

And that's that! Hope you guys enjoyed this. I know this problem seems pretty elementary for some, but I promise that as time goes on we'll be dealing with more challenging problems. If you plan to stick around and want to receive email notifications whenever I post a new problem, subscribe with your email at the very bottom! You can always unsubscribe :)

Edit: Thank you to DrBones and philippachigalla for catching a mistake! My method 1 had a typo in it :)
 


Join the discussion:

Log in or Sign up to vote and leave comments.


DrBones | May 12, 2019, 3:05 a.m.

How does #1 find the sum of all these numbers?  In fact, when I execute it myself, I get 467...the count of all the multiples of 3 and 5, not their sum.

2 | Reply
solidiquis | May 12, 2019, 3:13 a.m.
Did you run method 1 exactly as shown? I just checked and got the correct answer.
0 | Reply
philippachigalla | May 12, 2019, 3:21 a.m.
DrBones, you are correct. He did is only counting the multiples of 3 or 5. You can see the issue in the fourth line where he does `result += 1` instead of `result += i`.
0 | Reply
solidiquis | May 12, 2019, 3:22 a.m.
Ahh thanks guys! That was typo. I meant to increment by i and not 1. I'll fix that :)
0 | Reply

Dovahkiin | May 11, 2019, 7:22 a.m.
Subverted expectations
2 | Reply
solidiquis | May 11, 2019, 7:46 a.m.
lol
1 | Reply

philippachigalla | May 11, 2019, 7:18 a.m.

Hi guys. I'm new here. Does anyone want to be friends?

0 | Reply
philippachigalla | May 11, 2019, 7:19 a.m.
xD
1 | Reply
Dovahkiin | May 11, 2019, 7:29 a.m.
:)
1 | Reply
solidiquis | May 11, 2019, 7:45 a.m.
lol
0 | Reply

Subscribe to be notified about new blog entries!

Email