• more randomer than you (unregistered) in reply to DaStoned
DaStoned:
It's a puzzle. Programmers don't solve puzzles for work.

I'd solve it similarly. I don't give a crap about puzzles and solving them. The computer does all the work, gives me the answer and we can all continue with more pressing matters. Brute-force is faster than coding a more intelligent algorithm.

And when business comes to you with a problem that reduces to solving this for numbers 1-1000, I'm sure they would love to sit around a trillion years or so whilst your computer solves a problem which someone elses finished solving in half a second. This is why you will be stuck near minimum wage whilst real programmers earn the money.

• DeltaX (unregistered)

If you go for loop, then fastest approach is:

```long i = 2520;
while ((i += 20) < long.MaxValue)
{
for (int j = 20; j >= 11; j--)
{
if (i % j != 0)
break;
if (j == 11)
return i;
}
}
}
```
• Bored Bystander (unregistered) in reply to DeltaX
DeltaX:
If you go for loop, then fastest approach is:
```long i = 2520;
while ((i += 20) < long.MaxValue)
...snip...
```

If you are going to start at 2520 (using the knowledge that 2520 is the answer for N = 10) then you might as well increment by 2520 each time.

My solution using primes and the argument someone mentioned earlier that we only need the highest power of each prime less than N is:

```DEF Solve(n) (
DEF Primes() (
VAR l <- [];
EVERY l:put(SUSP 2:up \ NOT (\$ % l:values) = 0);
);
VAR r <- 1, t;
EVERY WITH p <- Primes() DO (
(t <- n >= p) // RET r;
REP WHILE t <- (n >= t * p);
r <- r * t;
);
);
```
• Peej (unregistered)

#include <stdio.h>

main () { int i; int primes = {2, 3, 5, 7, 11, 13, 17, 19}; int res = 1;

``````    for (i = 0; i < 8; i++)
{
int val = primes[i];

while (val <= 20)
{
res *= primes[i];
val *= primes[i];
}
}

printf ("%d\n", res);
``````

}

• Tepsifüles (unregistered)

The comments are The Real WTF indeed. Or I have been trolled by half a dozen people simultaneously, I can't decide.

• Laenulfean (unregistered)

Well, he did some optimizations here as one can see. But I wonder, why he didn't skip the numbers 3,6,7,8,9 as well?

• itsmo (unregistered)

You're all wrong - the most appropriate answer is 'who cares?'

• Nina (unregistered) in reply to Max

Yes, of course. What you do is to look at the different primes that are in the prime factorizations of all the numbers, i.e., if the number is required to be divisible by 6 its prime factorization needs to contain one 2 and one 3.

So, actually, this problem should be done by paper and pencil and then it is a simple calculation: 1=1 2=2 3=3 4 = 22 (add second 2) 5=5 (6 = 23, already contained) 7=7 8=222 (add third 2) 9=33 (add second 3) (10=25) 11=11 (12=223) 13=13 (14=27) (15=35) 16=2222 (add fourth 2) 17=17 (18=233) 19=19 (20=22*5)

Number must have this prime factorization: 12325723111321719 = 232792560

• Vollhorst (unregistered)

2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 2 3 2 5 3 7 4 9 5 11 6 13 7 15 8 17 9 19 10 2 3 2 5 1 7 4 3 5 11 2 13 7 5 8 17 3 19 10 2 3 2 5 1 7 2 3 5 11 1 13 7 5 4 17 3 19 5 2 3 2 5 1 7 2 3 1 11 1 13 7 1 4 17 3 19 1 2 3 2 5 1 7 2 3 1 11 1 13 1 1 4 17 3 19 1 2 3 2 5 1 7 2 3 1 11 1 13 1 1 2 17 3 19 1 2 3 2 5 1 7 2 3 1 11 1 13 1 1 2 17 1 19 1

2 3 2 5 7 2 3 11 13 2 17 19

= 232792560

• Azeroth (unregistered) in reply to Nina
Nina:
Yes, of course. What you do is to look at the different primes that are in the prime factorizations of all the numbers, i.e., if the number is required to be divisible by 6 its prime factorization needs to contain one 2 and one 3.

So, actually, this problem should be done by paper and pencil and then it is a simple calculation: 1=1 2=2 3=3 4 = 22 (add second 2) 5=5 (6 = 23, already contained) 7=7 8=222 (add third 2) 9=33 (add second 3) (10=25) 11=11 (12=223) 13=13 (14=27) (15=35) 16=2222 (add fourth 2) 17=17 (18=233) 19=19 (20=22*5)

Number must have this prime factorization: 12325723111321719 = 232792560

Thank you! Number theory has always somewhat confused me, but your explaination makes sense.

• Fred Weigel (unregistered) in reply to ideo

Not the way to the answer

The answer is derived by taking the factors of each number from 1 to 20, and picking the largest number of each prime factor, and multiplying those together.

Example:

2 4 8 16 appear (2 22 222 2222). So, the answer has at least 4 "2" factors. (actually, it will have exactly 4 "2" factors). Since the Euler question gave the answer for 1 to 10, I'd multiply that by 11, 13, 17, 19 and 2 (to accommodate 16).

So, the program is:

"print 2520 * 11 * 13 * 17 * 19 * 2"

232,792,560

Of course, I couldn't write it PHP.

• (cs) in reply to Resistance
Resistance:
TRWTF is that still many commenters think that optimizing the loop is the way to go. You don't have to search for the answer, you have to calculate it. And it's basic math they teach at university

And if an interviewee didn't happen to take that course? Or maybe they didn't go to university at all. Did you know people can program computers without having gone to university?

• Steve (unregistered)

Wow, are you guys still arguing over this? Come on, let's all go and argue over the new articles.

• Anon (unregistered) in reply to the real wtf fool
the real wtf fool:
And if an interviewee didn't happen to take that course? Or maybe they didn't go to university at all. Did you know people can program computers without having gone to university?

Then the question did what it was supposed to and showed that the candidate sucked at math. Amazingly enough “being able to code” is not always the only job requirement for some developer positions.

• Ilya Ehrenburg (unregistered) in reply to the real wtf fool
the real wtf fool:
Resistance:
TRWTF is that still many commenters think that optimizing the loop is the way to go. You don't have to search for the answer, you have to calculate it. And it's basic math they teach at university

And if an interviewee didn't happen to take that course? Or maybe they didn't go to university at all. Did you know people can program computers without having gone to university?

Actually, it's elementary arithmetics they teach in school (if you live in a country where that isn't taught in school, flee as fast as you can). Anybody (except the mentally handicapped) from the age of 15 onwards should be able to come up with at least byuu's algorithm after less than five minutes of thinking. If you're being interviewed for a position in a math-heavy environment and you can't immediately come up with

```foldl' lcm 1 [n `div` 2 .. n]
```

or the equivalent (or something better) in your language of choice, you're definitely not to be hired.

Granted, if you don't know before the interview that it's a math-heavy environment (but you should know), it would be unfair to ridicule you for offering an increment and test loop - as long as it's reasonably coded. The CodeSOD contains many WTFs even if you don't count the algorithm. Most has been mentioned before, but:

• Giving an arbitrary upper bound for the loop (obviously not knowing but just assuming it's large enough): WTF
• Incrementing the loop variable by 1 and immediately calculating \$num = 20*\$i: WTF
• Fourteen nested ifs: WTF
• Not testing divisibility by 2, 4, 5, 10, but by 3, 6, 7, 9: WTF
• tbrown (unregistered) in reply to Franz_Kafka
Franz_Kafka:
tbrown:

Ding ding ding!! Yes!!

For example, I can't tell you how much I dislike candidates whose first response, for almost any question, is "I would do a google search, look through MSDN KnowledgeBase, etc. and see what other people have done to solve this problem, evaluate their solutions, yadda yadda yadda..." If someone has to resort to a literature search for every frickin' coding problem that rises up and smacks 'em in the face then they're not going to be the most productive of developers, are they?

But most of all, that type of answer makes it completely impossible to judge how good a developer a candidate really is (or might be). I guess I need to be armed with a laptop and turn it over to the candidate and say, "go for it, you have 30 minutes to give me a working solution in C# code!"

You'd hate me. When I don't know something, I google it to find out. What the hell else are you going to do?

But would you blindly respond to any interview question with that answer, especially an interview question that asked you to sketch out some code (or even pseudo-code)?

I'm not kidding, I've asked things like "write some <insert language of choice> code to insert a node into a linked list." and gotten the "I'd google it" answer. That's just not going to fly (east, south, or north)!!

(captch: enim -- "mine" backwards, which means it must be yours)

• Big deal (unregistered)

I don't get why this is so bad. Sure it's brute force but once the answer is known it doesn't change and the whole function can be replaced with "return euler_20" or such.

• kl (unregistered) in reply to DaStoned

Programmers don't solve puzzles for work.

You must be a sad coding monkey.

• Josh folder (unregistered)

Wow, that gave me a headache!

Jiff www.privacy.de.tc

• Less (unregistered) in reply to More

Seriously. My first reaction to seeing the solution was that this person will write some seriously unmaintainable garbage code. I don't even need to know if the solution produces the right answer or not.

On the other hand, COBOL programmers write code like this all the time. It's virtually standard practice and they completely don't understand why I cringe every time I see huge multiply nested trees of if statements.

• Rörd (unregistered)
```#!/usr/bin/bc -q
16*9*5*7*11*13*17*19
quit
```
• pyro (unregistered) in reply to mauve

It's worth considering that it's a one shot program. Once it spits out it's answer, it can be replaced by a single print statement.

A GOOD programmer recognizes that and realizes that it won't take all that long to brute the answer.

In that case, it's the right solution. It's trivially correct and wastes minimal developer resources.

If you want a more elegance in the solution, you need to pose a problem that actually calls for it or specify that you want the most elegant rather than the simplest solution.

• guest (unregistered)

Here is a python solution (a solution like this could be better, though.)

```def factors(n):
factors = []
i = 2
while i <= n:
if n % i == 0:
factors.append(i)
n = n / i
else:
i += 1
return factors

def mergeFactors(listA, listB):
a = 0
b = 0
result = []
while a < len(listA) and b < len(listB):
if listA[a] < listB[b]:
result.append(listA[a])
a += 1
elif listA[a] > listB[b]:
result.append(listB[b])
b += 1
else:
result.append(listA[a])
a += 1
b += 1
result += listA[a:]
result += listB[b:]
return result

def allFactors(n):
factorList = 
for i in range(2, n):
factorList = mergeFactors(factorList, factors(i))
return factorList

def solution(n):
factorList = allFactors(n)
result = 1
for i in factorList:
result *= i
return result
```
• MM (unregistered) in reply to itsmo
itsmo:
You're all wrong - the most appropriate answer is 'who cares?'
Despite how that sounds, it's actually correct. For every programming problem, whether in an interview or not, the very first things a programmer needs to determine are "who cares" and "why". Without knowing the purpose behind the requirement, there's no way to make any meaningful assumptions about it. For any programming task someone is asked to do in an interview, they should start by asking the interviewer about what it's (allegedly) needed for.

For some purposes, a brute-force method really is the best solution, since it's both quick to write and easy to understand (and therefore easy to maintain and adapt if necessary). My solution in this case would involve an inner loop rather than all the nested ifs in the WTF solution, but would actually be even less efficient (since the inner loop wouldn't exclude the 10, 5, and 2).

If for some reason (though I can't fathom what), they actually needed to re-calculate a fixed constant like this repeatedly, then it might be worth optimizing for speed. I'm guessing that working out the prime factors solution would be a good way of doing that. (If it came up in a real-world scenario, I'd want to look into why we were re-calculating constants often enough for speed to be an issue, though. It sounds like some really poor design in the overall structure of the program. In an interview, I'd point out that problem to the interviewer, though I'd do the excercise anyway.)

If an interviewer can't answer what the reason for the requirement is, then I'd generally favor code clarity over speed optimization, particularly in a situation like this where I can't think of any likely use that would involve running the query more than once. In this case, I'd go with the brute-force approach.

• MM (unregistered) in reply to Coward
Coward:
Any respectful programmer have writen his share of code, why don't the interviewer just ask for that? Makes it a lot easier on everyone.
Not every programmer does a lot of programming on their own personal time. Programs written for work belong to the employer and not to the programmer. A programmer normally won't have access to that code once they've left that job and are looking for another.

(And this is ignoring the even more obvious problem that if someone did have code samples to provide, there would be no way for the interviewer to know who actually wrote them.)

Ruby + mathematics:

```require 'rational'

def lcm_of_set(set)
set.inject(1){|acc, v| acc.lcm(v) }
end

puts lcm_of_set((1..20).to_a)```
• 33mhz (unregistered) in reply to DaStoned

Only if you simply don't have the ability to come up with a better algorithm. You could break everything up into prime factorizations and then you'd only have to iterate through 20 numbers instead of starting from a Really Big Number pulled out of a hat and then iterating downwards.

• przemek klosowski (unregistered)

Use numerical computing environment for numerical work, Octave in this case:

octave:26> lcm(1:10) ans = 2520 octave:27> lcm(1:20) ans = 232792560

OK, that's cheating a little bit. Let's do it by hand, so that it could be reimplemented in PHP

n=20; ff=zeros(n,n); for i=1:n; f=factor(i); for j=f; ff(i,j)++; end; end; prod((1:n).^max(ff)) ans = 232792560

Essentially, I am building an array ff(20,20) which contains the multiplicities of all prime factors of each number from 1 to 20. Then, max(ff) will contain the largest multiplicities of each factor. The answer is just product of all the factors raised to the power of those multiplicities.

greetings

przemek klosowski

• Tom Swirly (unregistered)

[context: professional for 25+ years; engineer at Google]

It completely solves the problem.

It's obviously correct.

You could write it in literally one minute and then run it while you came up with an optimized program.

The chances are that you'd run into the correct solution in the first few tens of thousands of numbers... the first few hundred ms.

• Jimmy the Geek (unregistered)

This is not a WTF. He solved the problem and didn't do any premature optimizations.

Making code work first and then optimizing later is how you should always write code. And only optimize if a profiler says it will actually do some good.

• Cale Gibbard (unregistered) in reply to complete looney

Factoring numbers into products of primes can be somewhat expensive in general though. (Though, for a bound this small, it's obviously not a problem.)

Somewhat better way: Notice that we are computing the least common multiple of the numbers 1 up to 20. The least common multiple of two positive numbers is their product divided by their greatest common divisor. In Haskell:

```> lcm a b = a*b `div` gcd a b
>  -- NB: div is integer division.
```

The GCD of a pair of numbers can be computed recursively by the famous Euclidean algorithm: The GCD of any natural number a and 0 is just a. Otherwise, the GCD of a and b is equal to the GCD of b and the remainder after dividing a by b.

```> gcd a 0 = a
> gcd a b = gcd b (a `mod` b)
```

Of course, both of the above functions are already defined in the Haskell Prelude (and handle edge cases like negative numbers better than these).

We then get the result by folding the lcm function over the list of numbers [1..20], (note that 1 is an identity element for lcm).

```> solution = foldr lcm 1 [1..20]
```

And we can try this code:

```*Main> solution
232792560
```

Of course, due to the ingenuity of the Euclidean algorithm, this is also quite efficient for larger numbers (though eventually you would want to do a strict left fold to avoid running into evaluation stack issues):

```*Main> foldr lcm 1 [1..10000]
5793339670287...(4329 digits snipped)...0800000
```
• Pizzaman (unregistered) in reply to DaStoned

You just explained why every webpage I load lately runs like molasses in January.

• Cope with IT (unregistered)

Hmm, to me it look like 0 (zero) is, in fact, a number. And it's divisible by all numbers (except itself) without remainder.

Of course putting a constraint on the problem (like: find an integer larger than zero...) makes the problem interesting (read: a bit harder to solve).

• vteg (unregistered) in reply to snoofle

Come on people. This is not difficult enough to be a riddle or puzzle. It is just testing basic programming skill, which the applicant clearly didn't have.

If your answer to this question on an interview is 'I don't have to solve this because I won't get this exact problem in real life', their answer is going to be : 'Next please!'

• prime1 (unregistered)

I was told the real wtf here is writing a search loop for a 6th grade math problem:

``` #!/bin/sh
echo \$[ 2520 * 11 * 13 * 17 * 19 * 2 ]
```

But then: why a php developer who is at least 10 years out of school/univerity would need knowledge about lcm is a riddle to me.

• (cs) in reply to vteg
vteg:
Come on people. This is not difficult enough to be a riddle or puzzle. It is just testing basic programming skill.
Wrong! If you follow the link back into the forums, where this article was taken from, in the comments there the original poster explains that their company frequently deals with complex mathematical problems and that the intention is to test the mathematical knowledge of the candidates as much as their coding ability. Given that extra information, then yes, this is a poor attempt. But given that you lot are *still* debating this rather than actually doing the research into the full details, I think you *all* fail the interview test and will not be getting jobs with me any day soon ;^)
• Geek (unregistered)

The real WTF is:

Why write 33 lines of code if you can simply do it by mental arithmetic?

• Tony Vegas (unregistered)

All interview questions need not be smart or logical, and they all are not about a single right answer, but often about how you think and respond to the situation presented to you.

Jeebus, is this what I'm getting myself into after college?! Working with a bunch of nimrods bitching about the setup rather than just doing the work?

• (cs)

This came up on a forum I hang out on. I wrote the "obvious" lcm solution. Someone else wrote the "obvious" loop.

On a moderately decent machine (couple GHz), his program needed 16 seconds of runtime, mine about 2 microseconds.

I know premature optimization's bad and all, but really, an exponential solution is a bad thing when an N*log(N) is trivial and fairly obvious.

• (cs)

Honestly, if someone is going to ask me a dumb question like that to test my programming skills I'm going to give them a dumb answer.

Sure it's not the most efficient or elegant code but it works. Can you really expect much more when asking someone to reinvent the wheel during a job interview

• bucket (unregistered)

You guys should use that piece of code to write your comments. Page 1 has about all the real comments, and the pages thereafter are just reiterations of the same comments. Heck, I'm sure someone even mentioned this before me.

• hansel (unregistered) in reply to Ren
Ren:
Anonymous:
This is what you call simple programming task?

Yes.

My web development team comes across problems like this every day. Heck, Ajax is impossible to develop with unless you wrote a doctoral dissertation on the Collatz Conjecture and attempted to solve Fermats theorem in part.

• Wulf0r (unregistered)

This might not be the Boing problem but it's at it's core a math question. There are two types of math problems: solved and unsolved ones. You aren't going to work on unsolved math problems unless you actually studied math and the solved ones are absolutely trivial to look up. Same goes for sorts. If I absolutely can't use a libary I'll wiki it and copy and paste it from there ...

If you want to know how good someone codes just require that they submit code samples. This riddle shit is not going to get anyone anywhere.

• captain obvious (unregistered)

This is actually quite a challenge in PHP. In almost any other language, it is fine and might be done in 1 line.

This is the best I got (with the added criteria of doing it for any input number and doing it fast):

The result:

Smallest number cleanly divisible by numbers 1..20 is 232792560 Processed in 0.281 ms

Code:

<?php define('DIVISIBLE_UP_TO', 20); \$startTime = microtime(true); // Multiplier - used to only check feasible numbers \$multiplier = 1; // Optimise multiplier with product of prime numbers in 1..input for (\$n = 2; \$n <= DIVISIBLE_UP_TO; \$n++) { for (\$i = 2; \$i <= sqrt(\$n); \$i++) if (\$n % \$i == 0) continue 2; \$multiplier *= \$n; } // Pre-configure loop variables \$n = 0; \$loopStart = floor(DIVISIBLE_UP_TO / 2) + 1; \$loopEnd = DIVISIBLE_UP_TO - 1; // Brute force check for numbers deemed feasible while (\$n += \$multiplier) { for (\$i = \$loopStart; \$i <= \$loopEnd; \$i++) { if (\$n % \$i != 0) { break; } elseif (\$i == \$loopEnd) { break 2; } } } \$answer = \$n; \$execTime = round((microtime(true) - \$startTime) * 1000, 3); echo "Smallest number cleanly divisible by numbers 1..".DIVISIBLE_UP_TO." is \$answer<br />"; echo "Processed in \$execTime ms
";
• captain obvious (unregistered) in reply to captain obvious

Sorry, why can't we edit comments by the way?

```<?php

define('DIVISIBLE_UP_TO', 20);

\$startTime = microtime(true);

// Multiplier - used to only check feasible numbers
\$multiplier = 1;

// Optimise multiplier with product of prime numbers in 1..input
for (\$n = 2; \$n <= DIVISIBLE_UP_TO; \$n++) {
for (\$i = 2; \$i <= sqrt(\$n); \$i++)
if (\$n % \$i == 0)
continue 2;
\$multiplier *= \$n;
}

// Pre-configure loop variables
\$n = 0;
\$loopStart = floor(DIVISIBLE_UP_TO / 2) + 1;
\$loopEnd = DIVISIBLE_UP_TO - 1;

// Brute force check for numbers deemed feasible
while (\$n += \$multiplier) {
for (\$i = \$loopStart; \$i <= \$loopEnd; \$i++) {
if (\$n % \$i != 0) {
break;
} elseif (\$i == \$loopEnd) {
break 2;
}
}
}

\$execTime = round((microtime(true) - \$startTime) * 1000, 3);

echo "Smallest number cleanly divisible by numbers 1..".DIVISIBLE_UP_TO." is \$answer<br />";
echo "Processed in \$execTime ms";```
• (cs) in reply to the real wtf fool
the real wtf fool:
Jokes aside, let's say you were making a web application (it was a PHP interview after all). You use brute force instead of taking 2 minutes to come up with something better (it's not a hard question).

If it is so easy to come up with a better solution in 2 minutes why didn't you? Remember no googling is allowed as this is an interview, and if you already knew an approach to finding LCDs then it has become a test of interviewee knowledge rather than skill and so worthless.

At the very least I would expect a programmer to have used a second for loop instead of nested ifs. From a good programmer, I would expect a basic knowledge of how arithmetic works, and the understanding that, if a number is divisible by 16, it's also divisible by 2, 4, and 8.

• killerP (unregistered) in reply to BLEEE

Well.... If you want to hire twice as many people to get the same Job done. And use twice the computers to have users wait twice as long to ..... You get the point. Recognizing patterns like this is what I would expect from any programmer.

• Zoinks (unregistered) in reply to Jackson
Jackson:
Can anyone solve this:

http://projecteuler.net/index.php?section=problems&id=202

Hint: it's all about primes. Many ProjectEuler problems are.

I like the fact that so many of the problems have obvious (but naive) solutions that will fail using 32-bit or 64-bit integers, or else take eternity to run :) Some of them are too mathsy for me, but there's always mathsworld.wolfram.com (and others) for mathsy research.

I particularly like the latest problem, as I designed a solution for a similar (but 2D) problem years ago.. it was O(n^4), but faster than any O(n^2) or O(n lg n) implementation! O() only gives a guide as to the shape of the upper bound on worst-case runtime.

• neophrene (unregistered) in reply to DaStoned
DaStoned:
It's a puzzle. Programmers don't solve puzzles for work.

I'd solve it similarly. I don't give a crap about puzzles and solving them. The computer does all the work, gives me the answer and we can all continue with more pressing matters. Brute-force is faster than coding a more intelligent algorithm.

Yeah programmers should know absolutely nothing about math so some space remains in their brain and they can simultaneously remember about 10 symbols instead of 7, and write 400 lines spaghetti functions instead of 20 lines clean ones. The last thing you want is a programmer that heard once in her life about LCM. Also, if a programmer knows about lots of simple algorithms, complexity theory, graph theory, (depending on what they are applying for, just having heard about could be enough), you should completely refrain from hiring her. The worst would be a programmer that actually knows that something else than imperative programming exists and when it should be used. No indeed a programmer able to write quantified proposition would be worse. You do not even want a programmer that would google for a smart solution for such well known problems, not even speaking about a programmer who indeed is equipped with a real brain featuring a state of the art neural network.

Maybe I know you? Are you the guy who delivered me some code where you wrote a function trying every even natural number from 0 to whatever the computer could handle, returning 1 if it matched with its parameter and 0 if the loop complete while no match has been found?

Please do the humanity a favour get a new job more in line with your abilities.

• neophrene (unregistered) in reply to Tom Swirly
Tom Swirly:
context: professional for 25+ years; engineer at Google
So why aren't you smart?
Tom Swirly:
You could write it in literally one minute and then run it while you came up with an optimized program.
Or you could write a syntaxically much better program with less WTF repetitions and save 30 seconds, or even better you could instantly recognize an elementary math problem and know its solution - construct its solution, or google for the solution (if allowed).

The ultimate approach would be not to apply for a job where math knowledge is requiered if you don't have any math knowledge.