Euler: Problem 1

In a vain attempt to become productive and cultivate motivation and some kind of order into my otherwist Street Fighter 4 driven life I’m attempting to get all of the Project Euler puzzles done and to write a little bit about my solution and writing a better solution. In some, probably most, cases, I will also have to go through some theory of how I got to the solution.

The first puzzle has to do with finding the sum of a series of natural numbers. It’s very close to a question that I’ve added to our list of interview questions recently labelled FizzBuzz.

Write a program that prints the numbers from 1 to 100. But for multiples of three print “Fizz” instead of the number and for the multiples of five print “Buzz”. For numbers which are multiples of both three and five print “FizzBuzz”.

If you know how to program, or program on a regular basis the answer to this is quite straight forward and has the following steps.

  1. For each number, starting at 1 and ending with 100
  2. If the number divided by three has zero remainder output Fizz
    • If the number divided by five ALSO has a zero remainder output Buzz
  3. If the number divided by five has zero remainder output Buzz
  4. Otherwise, output the number

What we can do here, is replace the outputting of Fizz and Buzz with a summation of that number giving us the following, simpler pseudo code or flow.

  1. For each number, starting at 1 and ending with 100
  2. If the number divided by three has zero remainder, add it to the ‘output’.
  3. OR If the number divided by five has zero remainder, add it to the ‘output’.
  4. Otherwise, do nothing.
  5. After we reach 100, print ‘output’

The more important thing about this is that we recognise the OR, a number that has a remainder of zero when divided by both five and three must not be added to the output twice.

The actual Project Euler first question is as follows:

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

To solve this with a programming language it is beneficial to know about modulo arithmetic and the modulo operator, but I don’t have time to go in to this at the moment.

In future I hope to go in to other peoples solutions and how optimization is brought into Project Euler.

About these ads

One Response to Euler: Problem 1

  1. airefall says:

    Thanks for the hint on the OR, I thought I had the right answer but forgot that I shouldn’t add numbers that are multiples of 3 AND 5. A simple else-if solved it.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

Follow

Get every new post delivered to your Inbox.

%d bloggers like this: