I really like "make it work, then make it fast" approach.
First implement a naive solution that works, then make it fast if necessary.
Starting out with the attitude of best solution possible might be very time consuming.
I'm not really talking about premature optimization here (on that, I completely agree). It's of course always a balance, because you don't want to get caught in analysis paralysis. But in general I'd say it's still better to 'think before you act'. Otherwise you might be devoting a lot of time and energy to creating and then maintaining a complex solution while a simple one would have sufficed.
I wrote my initial comment because of the phrase 'That's the only proper way to do it.' which I disagree with.
Let's return to the initial problem from the post.
What is the smallest positive number that is evenly divisible by all of the numbers from 1 to 20?
There are no other requirements about code complexity, performance or anything else. Dwayne's solution is clever, but it requires a domain knowledge to understand what's going on. Moreover, it's less flexible for the case of different inputs.
A naive bruteforce solution is definitely slower, but the code intention is clear from the code itself and doesn't require some implicit wisdom.
So, I think both solutions are good and solve the problem. A concrete project's requirements is the most important part when choosing one solution over another.
Did you notice that all the posted solutions required the same domain knowledge?
If all the numbers from 1 to 20 divide the number then the number must be a multiple of all the numbers from 1 to 20.
Since we want the smallest such number it follows that we want the least common multiple of the numbers from 1 to 20.
Everyone has to make a similar deduction in order to even begin writing their solution.
Rather than writing a program to solve it I simply went ahead and did the LCM calculation by hand. The only extra domain knowledge required is knowing how to calculate the LCM of a set of numbers using prime factorization.
As much as I'd like to take credit for a clever solution, I must say that the prime factorization method is the standard way one learns to find LCM. (LCM using prime factorization)
The way I went about my explanation must have made the solution seem clever but my intention there was to describe a thinking pattern one might go through if they don't know much about LCM and how you'd reason your way from an initial answer (1*2*...*20) to the smallest possible answer.
Also, everyone else used the fact that LCM(a,b)*GCD(a,b) = a*b so that LCM(a,b)=(a*b)/GCD(a,b). Now that's not obvious, unless you look it up or you know why it's true which is based on prime factorization (which in itself is a nice proof, though that's beside the point).
I like your way of thought and clean explanation.
It's great when you can think deeply about the problem and find a solution without writing a line of code.
But there's also another way. Just convert the problem from the human language to the programming language and throw it to the computer to calculate the result.
What's better? It depends on the environment, because both solutions have their own pros and cons.
@Eugene: I should have elaborated what I meant with 'the only proper way'. I wasn't referring to the fact that Dwayne's solution was analytical/mathematical. I was pointing to the fact that he first analysed the problem before coming up with a solution. This has the benefit of often choosing simpler solutions over complex ones. Indeed, there was no explicit requirement for simplicity (or performance), but then maintainability never tends to be explicitly mentioned in requirements.
Dwayne's logic is essentially the following:
I need the smallest/simplest number divisible by all the numbers in the range (i.e 1->20)
Many numbers in that (or any) range are already divisible by others in that range, so all I need are the prime numbers
So I need to multiple all the prime numbers in that range
Note that the logic here is very straightforward and definitely not complex, is very flexible since it isn't limited to the range of the original requirement, can easily be amended when new requirements are added, and can in the future still be implemented as code when things go beyond simple arithmetic (with the added bonus that the choice of programming language is still entirely open).
As to domain knowledge, probably the most important lesson that most developers learn at some point is that domain knowledge is the cornerstone to success, and that knowing when and how to acquire it is an invaluable skill. To put it another way: the most productive software developers proactively talk to (domain expert) people and learn from them.
(though, as Dwayne mentioned, the domain knowledge here is quite limited. I would expect/hope that anyone who attempts this knows the concept of prime numbers, since it's so tightly coupled with the concept of divisibility).
Let's follow your algorithm for the range 1 to 10 (for simplicity).
Numbers in this range: 1,2,3,4,5,6,7,8,9,10.
Prime numbers in this range: 2,3,5,7.
Multiplication of these numbers: 2*3*5*7 = 210. Which is different from the correct answer 2520, so your algorithm is wrong.
Sometimes it's better to write a simple, stupid algorithm and let a computer to do the heavy work instead of doing all the work in your brain, which might be complicated and error prone.
You misunderstood. The explanation I gave is one of many ways someone can DISCOVER that what you need to do is to find the LCM of the numbers.
You do agree that the problem is implicitly asking you to find the LCM of 1,2,3,...,20?
Once you reach that point of understanding then you can do at least two things:
You can write a program that finds you the LCM. As all the coded solutions do.
You can use prime factorization to quickly compute the answer. As I did and it boils down to finding the highest powers of the primes in the given range which would be 2*2*2, 3*3, 5 and 7.
And I don't disagree with you. Start with brute force and improve. You'd then have something to test your optimizations, clever code etc against.
I really like "make it work, then make it fast" approach.
First implement a naive solution that works, then make it fast if necessary.
Starting out with the attitude of best solution possible might be very time consuming.
I'm not really talking about premature optimization here (on that, I completely agree). It's of course always a balance, because you don't want to get caught in analysis paralysis. But in general I'd say it's still better to 'think before you act'. Otherwise you might be devoting a lot of time and energy to creating and then maintaining a complex solution while a simple one would have sufficed.
+1 for 'think before you act'.
I wrote my initial comment because of the phrase 'That's the only proper way to do it.' which I disagree with.
Let's return to the initial problem from the post.
There are no other requirements about code complexity, performance or anything else. Dwayne's solution is clever, but it requires a domain knowledge to understand what's going on. Moreover, it's less flexible for the case of different inputs.
A naive bruteforce solution is definitely slower, but the code intention is clear from the code itself and doesn't require some implicit wisdom.
So, I think both solutions are good and solve the problem. A concrete project's requirements is the most important part when choosing one solution over another.
Did you notice that all the posted solutions required the same domain knowledge?
If all the numbers from 1 to 20 divide the number then the number must be a multiple of all the numbers from 1 to 20.
Since we want the smallest such number it follows that we want the least common multiple of the numbers from 1 to 20.
Everyone has to make a similar deduction in order to even begin writing their solution.
Rather than writing a program to solve it I simply went ahead and did the LCM calculation by hand. The only extra domain knowledge required is knowing how to calculate the LCM of a set of numbers using prime factorization.
As much as I'd like to take credit for a clever solution, I must say that the prime factorization method is the standard way one learns to find LCM. (LCM using prime factorization)
The way I went about my explanation must have made the solution seem clever but my intention there was to describe a thinking pattern one might go through if they don't know much about LCM and how you'd reason your way from an initial answer (1*2*...*20) to the smallest possible answer.
Also, everyone else used the fact that LCM(a,b)*GCD(a,b) = a*b so that LCM(a,b)=(a*b)/GCD(a,b). Now that's not obvious, unless you look it up or you know why it's true which is based on prime factorization (which in itself is a nice proof, though that's beside the point).
I like your way of thought and clean explanation.
It's great when you can think deeply about the problem and find a solution without writing a line of code.
But there's also another way. Just convert the problem from the human language to the programming language and throw it to the computer to calculate the result.
What's better? It depends on the environment, because both solutions have their own pros and cons.
@Eugene: I should have elaborated what I meant with 'the only proper way'. I wasn't referring to the fact that Dwayne's solution was analytical/mathematical. I was pointing to the fact that he first analysed the problem before coming up with a solution. This has the benefit of often choosing simpler solutions over complex ones. Indeed, there was no explicit requirement for simplicity (or performance), but then maintainability never tends to be explicitly mentioned in requirements.
Dwayne's logic is essentially the following:
Note that the logic here is very straightforward and definitely not complex, is very flexible since it isn't limited to the range of the original requirement, can easily be amended when new requirements are added, and can in the future still be implemented as code when things go beyond simple arithmetic (with the added bonus that the choice of programming language is still entirely open).
As to domain knowledge, probably the most important lesson that most developers learn at some point is that domain knowledge is the cornerstone to success, and that knowing when and how to acquire it is an invaluable skill. To put it another way: the most productive software developers proactively talk to (domain expert) people and learn from them.
(though, as Dwayne mentioned, the domain knowledge here is quite limited. I would expect/hope that anyone who attempts this knows the concept of prime numbers, since it's so tightly coupled with the concept of divisibility).
Let's follow your algorithm for the range 1 to 10 (for simplicity).
Numbers in this range: 1,2,3,4,5,6,7,8,9,10.
Prime numbers in this range: 2,3,5,7.
Multiplication of these numbers: 2*3*5*7 = 210. Which is different from the correct answer 2520, so your algorithm is wrong.
Sometimes it's better to write a simple, stupid algorithm and let a computer to do the heavy work instead of doing all the work in your brain, which might be complicated and error prone.
Huh? That's not the algorithm.
You misunderstood. The explanation I gave is one of many ways someone can DISCOVER that what you need to do is to find the LCM of the numbers.
You do agree that the problem is implicitly asking you to find the LCM of 1,2,3,...,20?
Once you reach that point of understanding then you can do at least two things:
You can write a program that finds you the LCM. As all the coded solutions do.
You can use prime factorization to quickly compute the answer. As I did and it boils down to finding the highest powers of the primes in the given range which would be 2*2*2, 3*3, 5 and 7.
And I don't disagree with you. Start with brute force and improve. You'd then have something to test your optimizations, clever code etc against.
Not exactly. You need to multiply by the highest powers of the primes in the range.
Yes.
And as you mentioned there are at least two ways to solve the problem. Both are valid.
We're on the same page 😉