Solving programming problems using PEDAC: Part 2. Sum of Multiples

This post is about the thought process and steps I went through when I practiced solving Sum of Multiples problem using a PEDAC process. I solved the problems using JavaScript. For a brief introduction of PEDAC, see the first post of this series here

The Problem

Write a program that, given a number, can find the sum of all the multiples of particular numbers up to but not including that number.
If we list all the natural numbers up to but not including 20 that are multiples of either 3 or 5, we get 3, 5, 6, 9, 10, 12, 15, and 18.
The sum of these multiples is 78. Write a program that can find the sum of the multiples of a given set of numbers. If no set of numbers is given, default to 3 and 5

Understanding the Problem

The first thing is attempting to determine inputs, requirements, constraints, and desired output. From the problem description, I determined there are two inputs:

1. A number to serve as the limit.
2. A set of factors. If factors are not given, default to [3, 5]

and the output is sum of all numbers, each of which is a multiple of at least one of the numbers in a given set of factors

Rules:

• All multiples must be less than the limit.

From the example described in the problem, I inferred the following rules:

• Factors must be natural number. Implicit rule: they must be greater than zero to avoid division by zero error
• Corollary: For there to be a possibility of multiples to be found, the first input (the limit) must be a natural number greater than zero as well.
• 15 appears once despite having two factors; 3 and 5. From this information I surmised that one of the rules is each multiple must be unique.

Below is how I broke down the problem.

Inputs:
  - number to serve as the upper limit of multiples.
  - a set of factors
    use [3, 5] as factors if a set of factors is not given
implicit rules:
    - all inputs must be natural numbers > 0
output:
  - sum of multiples of a given set of factors
  
  rules:
    - multiples must be < limit.
implicit rules:
    - each multiple must be unique
    
    from the example, the target is 20; and the factors are [3, 5],
    and the multiples are 3, 5, 6, 9, 10, 12, 15, 18
      - all multiples of 3 that are less than 20 are:
        3, 6, 9, 12, 15, 18
      - all multiples of 5 that are less than 20 are:
        5, 10, 15
        
        15 appears once despite being a multiple of both 3, and 5

If I were at job interview, I would ask for clarification here but for the purpose of this blog post, I made the following assumption:

A set of factors is considered to have not been given when the second argument is omitted.

At this point, I’m comfortable that I have broken down the problem into an easier to digest format, and fleshed out all the rules and requirements.

Mental Model

This is my summary of what the problem requires, and sort of a blueprint of how I plan to attack the problem.

Collect every unique multiple (of each factor) up to, but not including the limit, and return the sum of the multiples

Examples

Based on what I learned in using PEDAC process, and it makes a lot of sense, my approach is to come up with, at minimum, an example for every rule, and requirement from problem description; including implicit ones. Then I throw in some for edge cases and/or bad inputs. Some of these examples, and their expected outputs, were given with the problem.

I believe those examples are adequate to cover all rules / requirements. Onto next step: Data Structure

Data Structure

Here I thought about what needed to be done, based on rules, examples, and mental model; for it would dictate what data structure I will choose to work with. Below is what data structures I chose, and the reasons for doing so.

Integer:
  - need to do arithmetic operations
Arrays:
  -need to collect multiples
    - iterate factors to collect multiples of each one
    - includes to skip multiples that are present in collection
    - push unique multiples in collection
    - reduce the collection of multiples to get its sum

Algorithm

Not much thought process went on here. Referencing data structure part above, the algorithm essentially writes itself. I realized, after I was done writing the part, that while I was outlining my reasons for choosing that particular data structure, I inadvertently baked a kind-of-an-algorithm within it. I guess it explains why “Data Structure & Algorithm” tend to be grouped together in CS classes. But I digress.

- create empty array, multiples
- validate inputs
- forEach factor, iteratively increment it by itelf to
  get all its multiples that are < limit,
  - check whether multiples array includes current multiple
    -  if not, push the multiple into multiples array
- reduce multiples into sum of multiples and return it

Code

On this step, I started implementing the solution based on the algorithm. I started by keeping it simple, and left input validation for later.

The outline:

function sumOfMultiples(limit, factors = [3, 5]) {
  var multiples = [];
  
  // TODO: Validate inputs
  
  factors.forEach(collectFactorsUniqueMultiples);
  
  return multiples.reduce(sumMultiples, 0);
}

Next, I created collectFactorsMultiples and sumMultiples helper functions. After I defined all called functions, I ran the example inputs. All “happy path” examples returned expected outputs. Examples with bad inputs threw all kind of exceptions, since at this point, I hadn’t written the code to validate inputs.

After having a working code, I added input validation. Below is the final working code that satisfy all of the problem’s requirements.

Next, Using PEDAC process to solve Word Count problem