How to Solve a Problem 6: Smallest Common Multiple

 Recently, I came across this question on /r/learnprogramming

Question: 2520 is the smallest number that can be divided by each of the numbers from 1 to 10 without any remainder.What is the smallest positive number that is evenly divisible by all of the numbers from 1 to 20?

Well, how would you write a program to figure this out? 

The answer is not that difficult, but it involves a lot of prime numbers. 

The short version: we can "construct" the number by starting from 1 and work our way up to 20. 

1 is obviously 1

2 is obviously 2

3 however, will be 6, as it needs to be divisible by 2 and 3

4 however, is NOT 24, but 12, 

5 is 60

6 is 60 because 60 is already divisible by 6

7 is 420 

8 is 840 (remember, factors)

9 is 2520

10 is still 2520. 

Do you see a pattern? 


Let's say you need to calculate smallestMultiple of X. 

To get it, you need the PREVIOUS smallestMultiple. i.e. smallestMultiple(X-1). For simplicity, let's call it "prevSM"

If that is divisible by X, then that's the answer. return prevSM

If it's NOT divisible by X, then we need to figure out what factor to multiple it by, and try again. 

But how do we determine what to multiply it by? It depends on what X is. 

If X is a prime number, then we just return prevSM*X because the only factor is itself. 

But if X is NOT a prime number, then we need to try one of the factors making up X. 

Let's take X=8 for example. We know prevSM = 420

8 is NOT a prime number, it has a factor of 2 (multiple times). 

So we multiple prevSM by 2, and test it against 8. testSM=840, which is divisible by 8. So return testSM (which is 840). 

So, any idea how to code this yet? 

Hint: It's a loop. 

Still no clue? Here's my "optimized" version where I put in a few limits. I only do between 1 and 50, and I hardcode 1 and 2. No need to loop for those simple cases. 

The only thing that's slightly mysterious would be divisibleByPrime but that I leave up to you. It's pretty obvious how it works. 


function smallestMultiple(endRangeInt) {
    // input parameter is the end range, i.e. if we want smallest multiple from 1 to 10, we pass in 10
    // for computational limits, we are only accepting 1 through 50
    if (endRangeInt < 1) return 0;
    if (endRangeInt > 50) return 0;
    if (endRangeInt == 1) return 1; // obvious
    if (endRangeInt == 2) return 2;
    // we start from endRangeInt = 3
    let sm = 2;
    for (tCount = 3; tCount <= endRangeInt; tCount++) {
        //for each number in range, we try...
        console.log(`currently sm = ${sm} tCount = ${tCount}`)
        if ((sm % tCount) != 0) {
            // sm not divisible by tCount, but is tCount divisible by a prime?
            console.log(`sm ${sm} is NOT divisible by tCount ${tCount}, checking factors`)
            tdivisor = divisibleByPrime(tCount);
            console.log(`tdivisor = ${tdivisor}`)
            if (tdivisor.length > 0) {
                //we have at least one factor
                sm = sm * tdivisor[0]
                console.log(`sm ${sm} was multiplied by ${tdivisor[0]}`)
                    //verify
                if ((sm % tCount) != 0) {
                    // this factor not enough 
                    console.log("We have a problem, the multiplier is not enough! ERROR!!!!!!!!!!")
                } else {
                    console.log(`sm ${sm} verified as divisible by tCount ${tCount}`)
                }
            }
        } else {
            // sm is divisible by tCount
            console.log(`sm ${sm} is divisible by tCount ${tCount}`)
        }

    }


    return sm
}

This is the END of the output:

currently sm = 360360 tCount = 15
sm 360360 is divisible by tCount 15
currently sm = 360360 tCount = 16
sm 360360 is NOT divisible by tCount 16, checking factors
divisibleByPrime -- 2 added
tdivisor = 2
sm 720720 was multiplied by 2
sm 720720 verified as divisible by tCount 16
currently sm = 720720 tCount = 17
sm 720720 is NOT divisible by tCount 17, checking factors
divisibleByPrime -- testNum 17 is a prime number, no further test needed
tdivisor = 17
sm 12252240 was multiplied by 17
sm 12252240 verified as divisible by tCount 17
currently sm = 12252240 tCount = 18
sm 12252240 is divisible by tCount 18
currently sm = 12252240 tCount = 19
sm 12252240 is NOT divisible by tCount 19, checking factors
divisibleByPrime -- testNum 19 is a prime number, no further test needed
tdivisor = 19
sm 232792560 was multiplied by 19
sm 232792560 verified as divisible by tCount 19
currently sm = 232792560 tCount = 20
sm 232792560 is divisible by tCount 20

Obviously, not the whole output. And this may fail at the higher numbers. But it will work for up to 20 just fine. 



Comments

Post a Comment

Popular posts from this blog

Yet another take on recursion

Recursion is often one of the hardest things to "get" in programming, so when you have your "aha" moment, it's that much more amazing. Conceptually, it's not that hard to see, but how do you actually program one such?  First, realize that " recursion is a method of solving a problem where the solution depends on solutions to smaller instances of the same problem." Let us try something simple. Let's say... I want you to sum up the elements of an arbitrary array, let's call it arr. It can have any number of elements, and each element is an integer. For the purpose of this exercise, let's just say it's [1,2,3,4], but it can be any integer, and the array can be any valid size. And I want to you use recursion, not loop (no for or while or such statements).  Now, remember the definition: "solving a problem where the solution depends on the solutions to smaller instances of the same problem".  Let's call this function rsum (
Read more

How to Solve a Problem, with Examples

One of the fundamental tasks of a programmer is how to solve a programming problem, based on the specifications. Here is my attempt to solve such a problem, finally arriving at a validated answer.  If you've been on hackerrank.com, you may have seen this problem before. It's Fraudulent Activity Notifications .  TL;DR: given an array of arbitrary length (let's say it can go to 1x10^6). Each number in the array is expenditures for each day... It can range from 0 to 200 (and is always an integer). You are also given a number "d", that's the number of days you need to LOOK BACK to calculate the window. You need the median value of that window. If the next value is larger than or equal to twice the median, client is notified. Now, given arbitrary d, how many notifications had been generated, for a given array?  Example: you're given 6 4     10 20 30 40 50 60 6 is the size of the array: 6 entries. Window size is 4. First run, "10 20 30 40" Med
Read more

Problem Solving for Programmers: a Neglected Topic?

How often have you heard this story... it may be you, or someone you knew in class...  This person has no problem picking up syntax of a new programming language and even got the quirks of the language down. But when it comes time to write an actual program for an assignment, s/he has ZERO ideas about how to proceed. Just completely blanks out. Attempts to help with hints like "you need a loop", "you need a variable for X" results in one or two lines of code... and nothing else. Sounds familiar? This programmer never actually learned to problem-solve. S/he can learn things by rote, knew all the syntax, keywords, commands, etc. But has no actual understanding of the material. S/he would do great in a quiz or test, but fail completely on projects (or essay questions, if it's not programming). To badly paraphrase Sherlock Holmes' "You see but you do not observe", what we have here is a case if "you recall but you do not comprehend". I
Read more