• Coward (unregistered)

    I don't see the wtf. He got the right answer, sure, a bunch of ifs could be removed if he payed more attention to the properties of the numbers he have chosen. Why bother, though? It seems like he probably just rewrote the problem's question in PHP, that's excelent.

    Now, using if instead of &&, well, it might hurt performance a little bit, but really, who's counting?

  • Yuliy (unregistered)

    To those who are suggesting he is dumb for starting at 1 instead of 2520:

    The correct answer is 232792560. Congratulations. You've saved .001% of the runtime. My hats off to you.

    To those suggesting counting down from 20!: 2432902008176640000 is 20!, that'll take 10 billion times longer than counting up. TRWTF is definitely in the comments

  • (cs)

    Personally, there's no way I would come up with an elegant solution to that problem. Frankly, even though I've taken a ton of math throughout school I've forgotten most of it as my day to day life never demands it. So I would end up writing some sort of brute force method.

    That said, the code in the OP is a pretty poor way of doing it brute force wise. To me, writing it in such a way demonstrates that you're not thinking in terms of good programming practices.

    At the very least, you could do something like this (this is very off the cuff with not much thought behind it and I'm sure there's a better way to do it even via brute force):

    int gcd(int min, max){
  int returnVal;
  int tmp;
  boolean done = false;

  for(returnVal=max; !done; returnVal+=2){
    done=true;
    for(tmp=max; tmp>=min; tmp--){
       if(!returnVal%tmp==0){
         done=false;
         break;
       }
    }
  }

  return returnVal;
}

int gcd1_20(){
  return gcd(1,20);
}

    That of course ignores the initial information and math tricks of doing it elegantly. If I knew the elegant way of calculating it mathematically, I could reflect it better in my code. But I don't, that's what google is for. Therefore brute force. It's also not in php, but it can be easily ported to php.

    It's ugly, I know, but it's the first thing that pops into my mind on how to go about brute forcing it.

    Addendum (2008-10-08 14:34): Oh yeah, and my code should check for overflow as well to keep it from looping infinitely.

  • A Non E-Mouse (unregistered)

    Say what you like, but this is a good question. Not as good as asking them to write atoi, IMHO, but a good question nonetheless. When I've used this question at my company we have always favored interaction and dialogue over getting the math right. BTW, if you interact well -AND- get the math right, you're in.

    Read Chapter 15 of DeMarco & Lister's Peopleware. In short, you wouldn't hire a juggler without first having seeing him juggle... It's easy enough to argue about appropriateness of any question... for instance, instead of a math puzzle why not ask questions about how to parse XML and select a particular node? Well, that's stuff that's often readily looked up in online help; if you don't do it on a daily basis, why not look it up?

  • (cs) in reply to Mr^B
    Mr^B:
    I think it's "penny wise, pound foolish", "cent wise, dollar foolish" just sounds wrong.

    :)

    Touche.

  • jDeepBeep (unregistered) in reply to Pentium100
    Pentium100:

    The picture looks shopped.

  • GrandmasterB (unregistered) in reply to K&T
    At any rate, how would you determine if someone can write code? Do you just hire them based off their resume and have them design production systems for a few months? Sort of like a 2 month long (paid?) interview?

    Well, you can, um, ask them questions. I've never needed to resort to silly little tests like this one to determine if someone knows what they claim.

    Ask them about their projects, how they were structured, why they were structured, how they came to that decision, etc. For example, if they list 'AJAX' on their resume, ask them to describe to you how that works exactly. If they list 8 different sql servers they've worked with, ask them to describe the differences between them.

    If the interviewer is technically competent, they can smell out someone full of BS immediately. If they arent technically competent, they shouldnt be the one interviewing programmers.

  • Pentium100 (unregistered) in reply to jDeepBeep

    that picture may be, but the machine is real. I first saw it on Discovery Channel (could find the tape and rip it if you want). Oh, it also has a wikipedia entry. It also requires ~16MW of power...

  • GrandmasterB (unregistered) in reply to Addison
    Addison:
    DaStoned:
    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.

    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). What happens to your server when 10,000-100,000 requests come through at once?

    Last time I checked reducing processing requirements by 1000 fold was a good thing.

    If you're so concerned about speed, run this guys 'inefficient' function once, and put the results into an array in code, or in a db. Then you never have to run the process again.

  • Bored Bystander (unregistered)

    The solution in my favourite language (name withheld to avoid flaming):

    (2520 * 1:up) \ NOT ($ % 1:to(20)) ~= 0;

  • jDeepBeep (unregistered) in reply to Pentium100
    Pentium100:
    that picture may be, but the machine is real. I first saw it on Discovery Channel (could find the tape and rip it if you want). Oh, it also has a wikipedia entry. It also requires ~16MW of power...

    is impressed

  • (cs) in reply to Ren
    Ren:
    #!/usr/bin/perl $max = 20*19*18*17*16*15*14*13*12*11; print "Max: $max\n"; $starttime = time(); LOOP: while($i+=20) { for(11..19) { next LOOP if($i%$_); } print "Min: $i\nRunning time: ".(time()-$starttime)." seconds\n"; exit(0); }

    End result:

    ~$ ./asd.pl Max: 670442572800 Min: 232792560 Running time: 6 seconds

    Interviewer: Have you considered using your ten years of PHP experience to solve this problem? Ren: No. It's true that I'm practically omniscient in PHP by now, but the downside to omniscience in PHP is that you know, to the very core of your being, that the friggin thing blows chunks. I prefer Perl. Interviewer: Well, we were actually looking for a PHP programmer, but let that pass. Have you considered overflow? Ren: Look, are you looking for a Perl programmer or a sanitation engineer? Interviewer: I'm not sure that there's all that much difference, really; but, as I said, we were kind of hoping to leverage the tens of hundreds of grey cells you've invested in PHP programming over the years. Your solution multiplies ten numbers together. Each of them is of the order of 2^4. That would be roughly 2^40, wouldn't it? Ren: What's the problem? Just use a 64-bit computer. Jeez, you guys are lame. Interviewer: I guess all those Google sites that imply there are problems with 64-bit integers in PHP could easily be wrong; but, anyhow, we sell our software to a lot of Mom and Pop stores who only have 32-bit computers. Ren: Well, just use floating point arithmetic, then. That's the whole thing about the PHP type system. It hides this stuff behind the scenes. Floats handle up to 2^53. Problem solved. Interviewer: Sort of. This particular problem. Maybe. Except that PHP isn't all that accurate at printing floats out, either. Have you considered what happens when you glue a slice of toast, butter side up, on to the back of a cat, and then drop the cat? Ren: No, why? Is this another stupid interview question? Interviewer: You might well get asked it when you take your next interview, at McDonald's.

    See? A few times ... a very few times, these "puzzle" interviews actually make sense.

  • LEON (unregistered) in reply to Ren

    dude the php takes only 4 Secs to Finish so PHP > PERL :P

    Ren:
    #!/usr/bin/perl $max = 20*19*18*17*16*15*14*13*12*11; print "Max: $max\n"; $starttime = time(); LOOP: while($i+=20) { for(11..19) { next LOOP if($i%$_); } print "Min: $i\nRunning time: ".(time()-$starttime)." seconds\n"; exit(0); }

    End result:

    ~$ ./asd.pl Max: 670442572800 Min: 232792560 Running time: 6 seconds

    <?php
$start = time();

for ($i=1;$i<=99999999999;$i++) {
  $num = 20*$i;
  if ($num%19 == 0) {
    if ($num%18 == 0) {
      if ($num%17 == 0) {
        if ($num%16 == 0) {
          if ($num%15 == 0) {
            if ($num%14 == 0) {
              if ($num%13 == 0) {
                if ($num%12 == 0) {
                  if ($num%11 == 0) {
                    if ($num%9 == 0) {
                      if ($num%8 == 0) {
                        if ($num%7 == 0) {
                          if ($num%6 == 0) {
                            if ($num%3 == 0) {
                              exit('Otook '.(time()-$start).' '.$num);
                            }
                          }
                        }
                      }
                    }
                  }
                }
              }
            }
          }
        }
      }
    }
  }
}
?>
~
~
~
~

    BTW my code which by me looks better takes 46 sec's :

    <?$start = time();
$checking = array(19,18,17,16,15,14,13,12,11,9,8,7,6,3);
for ($i=1;$i<=99999999999;$i++) {
        $num = 20*$i;
        $die = 1;
        foreach($checking as $value)
                if($num%$value != 0)
                        $die = 0;
#        echo $i."\n";
        if($die == 1)  {
                exit("\n\nMtook".(time()-$start).'  '.$num."\n\n");
        }
}
?>
~

~
~
~
~
  • Ellie (unregistered)

    Thanks for the pointer to the great puzzles!

    For the algorithm I came up with...

    Compute the prime factors of all the numbers from x to 2 Eliminate the duplicate terms* Multiply the remaining terms for the win.

    • x=2 -> factorlist[] = (2,3,2,5,7,2,3,11,13,2,17,19);

    captcha: bene (Latin prefix for good or well.)

  • (cs) in reply to Strilanc
    Strilanc:
    The post gives the *really* naive solution, but applying lcm iteratively is still sortof naive. You can get a better asymptotic complexity, and a simpler algorithm, by generating then using a list of primes up to 20. 
    max = 20
#don't actually use fixed primes like this
#use a fast sieve to generate them
primes_up_to_max = [2,3,5,7,11,13,17,19]
n = 1
for p in primes_up_to_max:
	i = p
	while (i <= max):
		i *= p
		n *= p
print n

    Not picking, but you missed something there. If you solve your way, you get 9,699,690 (not right). Not divisible, for example, by 16 (2^4). Right answer would be 2^4 (for 16), 3^2 (for 9), 5,7,11,13,17,19 -> 232,792,560. Not primes, but prime factorization of EVERY number 1-20, then taking the largest count per number. 10 is covered by 2 & 5, so don't need anything extra. 9 is 3x3, and for 2 you have 2,4,8,16, so 2x2x2x2 gets it. Points for effort, though.

  • NonEulerian (unregistered)

    4 microseconds on my machine

    int step = 2*3*5*7*11*13*17*19;
int n = step;
do {
     int i = 0;
     for ( i=20; i>1; i-- ) {
          if ( n % i != 0 ) break;
     }
     if ( i == 1 ) break;
     n += step;
} while (true);
  • dave (unregistered) in reply to jimlangrunner

    Not picking, but running that code prints 232792560. The inner while loop is to get the 2^4/3^2 (you only need to find the max power of each prime < max to account for all prime factorizations < max).

  • An Old Hacker (unregistered)

    First, it is shocking how many of the "better" answers are incorrect. Incorrect code has negative value, people!

    Second, those defending brute force on the basis of "it doesn't take all that long to run" are idiots. What if the problem had been to run to 25? It's blatantly clear that the interviewee has no idea about actual runtime. The fact that it runs in less than an hour (day, year, century) is happenstance. O(n!) is really, really bad, and if I ever get a solution of that sort, I'm going to immediate raise questions with the customer about reuse.

    Third, the joker talking about asymptotic behavior for a problem this small is another sort of idiot. Behavior at the limit is just that--at the limit. At the limit, you dedicate a warehouse to servers that precalculate answers & do a lookup when you need an answer.

    Forth, this sort of loop nesting is a code stench. It is unmaintainable (same problem with some of the "improved" versions). Unmaintainable code has a strong negative component to its value. (Same problem with just hard coding the value--it's mAgick!)

    Fifth, the use of a problem from the internet is a WTF. If someone were to be working through the problem set in their spare time, their performance will be unjustly inflated. The best coding problems I've faced (by far) have come directly from production code/production problems.

    Sixth, interview code problems are entirely about approach. Someone who attacks twenty problems without ever asking for clarification or detail is a coding sUper gEnius. whoo! (That whoo! is the sound of the train whistle coming down the tracks that your dynamite shack is now on) Someone who presents this solution without interacting has just left a O(n!) s*** bomb in your code. Hire if you like manual minefield clearing as a hobby.

  • (cs) in reply to tbrown
    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!"

    (captcha: validus -- how apropos)

    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?

  • (cs) in reply to Geoff
    Geoff:
    Cute. My turn...(Common Lisp)

    (defun foo(n) (reduce #'lcm (loop for i from 1 to n collect i))) FOO

    (compile 'foo) FOO

    (time (foo 20)) Timing the evaluation of (FOO 20)

    User time = 0.000 System time = 0.000 Elapsed time = 0.000 Allocation = 252 bytes 0 Page faults 232792560

    I just want to bask in the lispy glow for a bit...

  • Jay (unregistered)

    Sure, there are more efficient solutions. But we have to know the assumptions behind the problem. As stated, this is a one-shot problem: Find the one number that meets this condition. Once you get the answer, there is no reason to ever run the program again. Under those circumstances, it makes a whole lot more sense to spend ten minutes writing a program that takes twenty minutes to run then to spend two days optimizing it to run in three seconds. Especially given that the brute force solution is much easier to verify than a more sophisticated solution.

    Reminds me of a programming contest that a math teacher in my high school conducted: Write a program that prints all the prime numbers less than 100. Winner is the program that produces accurate results with the fastest run time.

    The entry that had the fastest run time consisted of one line of BASIC code:

    10 print "2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41,
43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97"

    The teacher disqualified it. It wasn't my submission, but I wish it was: It's hard to imagine a more efficient solution.

    In real life, if a client tells me that as part of an advertising campaign they need to find a customer in Wisconsin who has bought more than $500 worth of widgets in the past year and who has a name that starts with a "W" because they want the advertising slogan to have all words that start with "W" -- sure, I could try to guess what similar advertising campaigns they might have in the future, generalize the problem by making a bunch of these specifics into parameters, develop user-friendly input screens for these parameters and optimize the queries to extract it. But it would all be a guess, so why bother? And it would take at least days of work, depending on how fancy I wanted to get. Surely the better solution would be to hand-type a SQL query with everything hard coded and give them an answer in ten minutes.

  • NonEulerian (unregistered) in reply to Ellie
    Ellie:
    Thanks for the pointer to the great puzzles!

    For the algorithm I came up with...

    Compute the prime factors of all the numbers from x to 2 Eliminate the duplicate terms* Multiply the remaining terms for the win.

    • x=2 -> factorlist[] = (2,3,2,5,7,2,3,11,13,2,17,19);

    captcha: bene (Latin prefix for good or well.)

    Very nice :-)

  • MAtho (unregistered) in reply to Ren
    Ren:
    ~$ ./asd.pl Max: 670442572800 Min: 232792560 Running time: 6 seconds
    (Perhaps I missed the point on what you meant by MAX)

    Surely Max is A LOT higher than that (you haven't multiplied by 2-10 ???? Which would give 2432902008176640000

    Which we could continually multiply by any of the numbers 1-20 ad infinitum.....???

  • Dan (unregistered) in reply to K&T
    K&T:
    At any rate, how would you determine if someone can write code? Do you just hire them based off their resume and have them design production systems for a few months? Sort of like a 2 month long (paid?) interview?

    Seriously, I've had tons of candidates that can tell me all the book definitions but when it came time to actually use those definitions in real code, they couldn't hack it. One guy event told me how cool recursion is, but when it came time to white board a method to search a file directory (and i gave him the needed classes and methods) he couldn't figure it out.

    Then offer test questions for which recursion makes the most sense and see if the candidates can spit something out. Like maybe "Assume qsort doesn't exist. Write a function that can quicksort an arbitrary sized array of integers". Or better yet, think back to complex problems that have been posed by your own in-house projects and ask candidates how they would have solved THOSE.

    I've only used the LCM algorithm once, in college, in a computer logic class. That's how generally useful it is and how likely a programmer is to remember it. So unless it is of dire importance to your specific project, it is of little value to require.

    Perhaps another test would be "can you turn this general algorithm description into PHP code?" similar to what we had to do in compiler construction when we wrote a full LR parser in Java. Of course a classmate and I both improved the algorithm by optimizing it down from hours to parse Pascal grammer, to under a minute. Too bad full LR parsers aren't used in the real world :)

  • byuu (unregistered)

    Obviously, the challenge is to get it to arbitrarily scale; eg go up to n=25, n=50, ... the biggest problem you have is the sheer size of the resultant integer.

    For n=1...42, you get 219060189739591200. Go higher than 42 or 43, and you need something above a 64-bit integer.

    Accepting the limitation of only being able to compute a 64-bit integer, I came up with the below code, which can compute the n=42 example above in a fraction of a second.

    It may still be O(n!) in the theoretical worst case (real world scenarios would be much lower), but since you can't exceed a 64-bit result without an arbitrary-precision integer library, I suppose it's probably the optimal solution when limited to built-in integer types.

    uint64_t find(unsigned count) {
  uint64_t value = count > 0;  //handle count = 0 case
  for(unsigned iter = 1; iter <= count; iter++) {
    uint64_t step = value;
    while(value % iter) value += step;
  }
  return value;
}

    It also only requires 32-bit integers to compute n=20.

  • Wow... (unregistered)

    http://codepad.org/N4U8ZK3g

  • Mr^B (unregistered) in reply to Pentium100
    Pentium100:
    Just a quick question:

    If someone told you to somehow dig a 1m wide and 0.5m deep hole, would you hire this machine to do the digging because the requirement might change to a 1km wide and 500m deep? Or just a man with a shovel?

    I would hire a man with a shovel, obviously. Because if the requirements changed to a hole 1km wide and 500m deep I wouldn't have lost anything by digging the original hole with a shovel, nor would I have to throw it away, nor re-do it a different way; there's been no lost effort and the hole is maintainable whatever method has been used to dig it.

    As analogies go, I've seen worse - but only just.

    :)

  • Steve (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.

    Oh yes, we are so impressed with your inability to grasp basic arithmatic, which you call "puzzles".

    Any idiot who graduated from elementary school should realize he doesn't have to check for 1 through 10 if 11 through 20 passed.

    But hey, you keep writing your bloated code and being smug about your incompetance.

  • Myth Monk (unregistered)
    <? $i = 2520; while (1) { if ( ($i%20==0) && ($i%19==0) && ($i%18==0) && ($i%17==0) && ($i%16==0) && ($i%15==0) && ($i%14==0) && ($i%13==0) && ($i%12==0) && ($i%11==0) ) { echo $i; break; } $i+=20; } ?>

    does it in 9 seconds on a 1.3GHz Athlon XP Thoroughbred.

    #include<stdio.h>

    int main() { int i = 2520;

    while (1) { if ( (i%20 == 0) && (i%19 == 0) && (i%18 == 0) && (i%17 == 0) && (i%16 == 0) && (i%15 == 0) && (i%14 == 0) && (i%13 == 0) && (i%12 == 0) && (i%11 == 0) ) { printf("%d\n", i); break; } i+=20; }

    return 0; }

    does it in 0.345 seconds on the same machine (not counting compile time)

  • byuu (unregistered) in reply to byuu
    byuu:
    It may still be O(n!)

    Oops, sorry. Still had that previous post in mind. I meant to say it is O(sum{1..n}), eg n(5) = (1+2+3+4+5) = 15, and not n(5) = (12345) = 120. Quite the difference there, but the overhead still grows exponentially as n increases (eg 5=15 (3x), 6=21 (3.5x), 7=28 (4x), ...)

  • dave (unregistered) in reply to byuu
    byuu:
    Obviously, the challenge is to get it to arbitrarily scale; eg go up to n=25, n=50, ... the biggest problem you have is the sheer size of the resultant integer.

    For n=1...42, you get 219060189739591200. Go higher than 42 or 43, and you need something above a 64-bit integer.

    Accepting the limitation of only being able to compute a 64-bit integer, I came up with the below code, which can compute the n=42 example above in a fraction of a second.

    It may still be O(n!) in the theoretical worst case (real world scenarios would be much lower), but since you can't exceed a 64-bit result without an arbitrary-precision integer library, I suppose it's probably the optimal solution when limited to built-in integer types.

    uint64_t find(unsigned count) {
  uint64_t value = count > 0;  //handle count = 0 case
  for(unsigned iter = 1; iter <= count; iter++) {
    uint64_t step = value;
    while(value % iter) value += step;
  }
  return value;
}

    It also only requires 32-bit integers to compute n=20.

    It's O(n^2). And simpler than all the other correct solutions. Nice :)

  • Matt (unregistered) in reply to I walked the dinosaur

    I'm laughing here that so many people are commenting that this is a horrifically complex math problem, or that "you'd need a degree in math to solve it", or proposing solutions with loops or GCDs or other such stupidness.

    The reason I got first post is because I went .. it has to be divisible by every prime less than 20 ... oh yeah, and repeated factors of 16 and 9 will get in the way too.

    So I open up calc and type

    16957111317*19

    and got first post.

    Any of you complaining about the complexity of this problem, or proposing any solution that involves any code AT ALL, then I am glad you do not work anywhere close to me.

  • Pentium100 (unregistered) in reply to Mr^B
    Mr^B :
    I would hire a man with a shovel, obviously. Because if the requirements changed to a hole 1km wide and 500m deep I wouldn't have lost anything by digging the original hole with a shovel, nor would I have to throw it away, nor re-do it a different way; there's been no lost effort and the hole is maintainable whatever method has been used to dig it.

    And how much time took him to write that program? 10 minutes? So, if the requirements changed, and he had to redo the program to support numbers up to 1000, he lost only 10 minutes of writing the initial program. Instead of googling (was he even allowed to do that?) how to find a smallest common multiple. But, I am not a programmer (can only make simple programs) so what do I know...

  • Prime Weevil (unregistered) in reply to Mogri
    Mogri:
    mcwyrm:
    Wow.

    max = 20 ans = 1

    for i = max to 1{ if mod(ans, i) != 0 then ans *= i }

    return ans

    Faster to type than your nested loops, and really - the obvious way to do it, no?

    Obviously wrong. It'll end up with too many factors of 2. If your loop ran 2 to max, then it'd work.

    What if Max = 5?? Even running the loop 2 to max you'd get 234*5 = 120?? Looking for 60, though...

  • 20% off! (unregistered) in reply to JimM
    JimM:
    they require a certain amount of mathematical knowledge - in fact they strike me as the solutions of people who have formally trained in maths and computer science. They are academically pleasing, but have no practical advantage given that any reasonable hardware will be able to brute-force mash the numbers in an acceptable timeframe (I'd guess you're looking at a few seconds at most).

    It instantly reminds me of a snippet of php code posted on wtf-like site in which case the force turned out not brute enough... The task was to resize image to fit given dimensions, and solution was like ( in c ) x=x0; y=y0; while ( x>xmax || y>ymax) { x*=0.99999; // decrease dimension a little bit more until image fits y*=0.99999; } image_resize(x,y); ... It were ok is hoster weren't killing processes consuming 100% cpu time. But it required too much math...

  • Blango (unregistered)

    A loopy Sol'n - No Knowledge of primes req'd - and it's kindof intuitive... reduce an array of integers from 1 to 20 into what needs to be added to element i to make (i+1) a factor of the product of the elements preceding it....

    Obviously, if you want extendibility you could generate the array on the fly, put all this into it's own method etc, etc, etc....

    #include <iostream>
#define ARRSIZE(X) (sizeof(X)/sizeof(X[0]))

using namespace std;

int main()
{

/* Could use a for loop to populate Array */
  int NumArr[] = {1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20};
  int NumArr_Length = ARRSIZE(NumArr);
  int counter = 0;
  int answer =1;

/* Get rid of common factors */
  for(int i = 0;i<NumArr_Length; i++)
  {
    counter=i+1;
    while(counter <  NumArr_Length)
    {
      if(NumArr[counter]%NumArr[i] == 0)
      {
        NumArr[counter] = NumArr[counter]/NumArr[i];
      }
      counter ++;
     }
  }


  for(int i = 0;i<NumArr_Length; i++)
  {
    cout << NumArr[i] << ",";
    answer*=NumArr[i];
  }
  cout << endl;
  cout << "The Magic number is " << answer << endl;
}
</pre>
  • Montoya (unregistered)

    I like PHP. I really do. But it's a web language. It's for building web sites & web apps. I wouldn't use it to solve any of the problems on Project Euler. Sure, it could be used to solve those problems... I just wouldn't do it. I also wouldn't take a job where I'm expected to be a math genius. That's not what my experience in web app development has led me to be.

  • Mr.'; Drop Database -- (unregistered) in reply to Tom JP
    Tom JP:
    There you go, punks. The factoring could be made more efficient, but it runs much better than the brute force crap. Runs for n=1000 in under a second. (result has 433 digits btw)
    Iterated LCM is simpler and faster, especially on large numbers.
    def lcm1_n(n):
  result = 1
  for i in range(1, n+1):
    a, b = i, result
    while a: a, b = b % a, a
    result = result * i // b
  return result
  • Mitch (unregistered)

    Yay fr Project Euler. Spend all my spare time on it. In about two months I haves solved 63. How about you guys?

  • ComputerSlayer (unregistered)

    6 minute attempt (written in notepad, thus untested):

    //
//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 number that is evenly divisible by all of the numbers from 1 to 20?
//
//
//

var $numfound=false; //was a match found?
var $num=1; //starting value to match
var $divisorstart=1;  //start of range
var $divisorend=20; //end of range
var $intlimit = 2147483647; //2147483647 is limit of signed int on 32-bit systems


//find the number

while(!numfound || $num<$intlimit){
	for(var $divisor=$divisorstart;$divisor<=$divisorend;$divisor++){
		if($num%$divisor==0){
			$numfound=true;
		}
		else{
			$numfound=false;
			$num++;
			break;	
		}
	}
	
}



//print the number

if($num==$intlimit){
	echo "Number not found";
}
else{
	echo $num . " is the smalled numer that is evenly divisible by all the numbers from " . 	

	$divisorstart . " to ". $divisorend;
}
  • Jackson (unregistered)

    Can anyone solve this:

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

  • Top3 Codd3r (unregistered) in reply to James

    In fact, I would go so far as to say that it was indented properly. :)

  • Pingmaster (unregistered) in reply to anoncow
    anoncow:
    jDeepBeep:
    I give the coder points for artistic value. Why, if you squint a little, it looks like a formation of geese flying south.

    East.

    You assume that we all face north when using a computer

  • Anon (unregistered)

    =LCM(A1:A20)

  • The Fake WTF (unregistered) in reply to Ren
    Ren:
    I can honestly say that in our product group we do not have a single application of prime numbers (well, I haven't read through all of the 10 million lines of code, but I'm pretty sure ;) ). Last time I used prime numbers was years back in high school.

    So you've never used encryption?

  • Coward (unregistered) in reply to An Old Hacker
    An Old Hacker:
    First, it is shocking how many of the "better" answers are incorrect. Incorrect code has negative value, people!

    Second, those defending brute force on the basis of "it doesn't take all that long to run" are idiots. What if the problem had been to run to 25? It's blatantly clear that the interviewee has no idea about actual runtime. The fact that it runs in less than an hour (day, year, century) is happenstance. O(n!) is really, really bad, and if I ever get a solution of that sort, I'm going to immediate raise questions with the customer about reuse.

    In this case you just want a number, you run it, if it turns out to be too long, you try to make it better. Why take some time thinking about it when a brute force solution could come up with the result in a few seconds? It was not told what's the purpose of the function, so why assume the worst?

    Why would someone want to reuse such function? It's purpose seems just to spit out a number, after the number is known the whole function is not even needed anymore. Are you proposing creating new problems for solve before you even got to solve the first one?

    Third, the joker talking about asymptotic behavior for a problem this small is another sort of idiot. Behavior at the limit is just that--at the limit. At the limit, you dedicate a warehouse to servers that precalculate answers & do a lookup when you need an answer.

    Forth, this sort of loop nesting is a code stench. It is unmaintainable (same problem with some of the "improved" versions). Unmaintainable code has a strong negative component to its value. (Same problem with just hard coding the value--it's mAgick!)

    What's unmaintainable about it? Mind clearing that up? Hard coding the value is just magic if you don't explain in your comments how you came to that result. If you explain, then it's pretty clear.

    Fifth, the use of a problem from the internet is a WTF. If someone were to be working through the problem set in their spare time, their performance will be unjustly inflated. The best coding problems I've faced (by far) have come directly from production code/production problems.

    Sixth, interview code problems are entirely about approach. Someone who attacks twenty problems without ever asking for clarification or detail is a coding sUper gEnius. whoo! (That whoo! is the sound of the train whistle coming down the tracks that your dynamite shack is now on) Someone who presents this solution without interacting has just left a O(n!) s*** bomb in your code. Hire if you like manual minefield clearing as a hobby.

    That's just bull. 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.
  • Coward (unregistered) in reply to Mr^B
    Mr^B:
    Pentium100:
    Just a quick question:

    If someone told you to somehow dig a 1m wide and 0.5m deep hole, would you hire this machine to do the digging because the requirement might change to a 1km wide and 500m deep? Or just a man with a shovel?

    I would hire a man with a shovel, obviously. Because if the requirements changed to a hole 1km wide and 500m deep I wouldn't have lost anything by digging the original hole with a shovel, nor would I have to throw it away, nor re-do it a different way; there's been no lost effort and the hole is maintainable whatever method has been used to dig it.

    As analogies go, I've seen worse - but only just.

    :)

    Only if the hole is in the same place. Even then, though, you have lost that effort because it won't make your life any easier whey you use a better hole making device.

    That talk about mintainable is much bull. We cannot know all possible uses of the code in advance. As long as you write something that's reasonable and your code is clean enough to be understood. If someday the time comes where the requirement changes, things can be changed because everyone will understand your code and will be able to modify it to make the new things work.

  • xXx (unregistered)

    WTF == Productivity measured in lines of code written per day.

  • Anon (unregistered) in reply to Coward
    Coward:
    In this case you just want a number, you run it, if it turns out to be too long, you try to make it better. Why take some time thinking about it when a brute force solution could come up with the result in a few seconds? It was not told what's the purpose of the function, so why assume the worst?

    It's idiotic to just assume that the code will never be used again and it's even more idiotic to write shit one-off code in an interview. In an interview you want to show your best not show your worst to save a couple of minutes. Most anyone can hack together a shit solution and in general companies prefer to pick new employees from outside the shit pile.

    I've personally been burned more than once when I had to spend time rewriting a “one off” piece of code that's now been used 20+ times (and much worse than that). It's generally good habit if nothing else unless you're really pressed for time or know 100% it will only be used once (which if likely rare).

    Why would someone want to reuse such function? It's purpose seems just to spit out a number, after the number is known the whole function is not even needed anymore.

    It's quite clear to anyone with any interview sense that a reusable solution shows much more of your abilities. In a more practical sense it's a decent assumption that your want a flexible solution if you have the time for one and aren't certain you don't need one. Note that in an interview you have the time for it and unless you ask (note: it's amazing what your mouth can be used for) you can't rule out it being used for other problem parameters.

    It's quite common where I work to first ask for a specific piece of data or code then to ask it with different parameters. Sometime the first one is enough, other times it's not and sometimes there's a big gap between the two. Sometimes things you assume shouldn't ever be asked for again are by someone working on something just slightly different. Sometimes requirements change and you need to modify your code appropriately then regenerate whatever it generates.

    I personally find it much more efficient to write decently sane and reusable code instead of making idiotic assumptions that waste more of my time in the long run. Then again that is job specific however like I said it never hurts to put some effort into an interview.

    Are you proposing creating new problems for solve before you even got to solve the first one?

    Of course, thinking ahead and planing are vital skills if you want to be anything more than a glorified monkey. If you don't do that then you end up in dead ends when coding, waste time and aren't worth it for any non code monkey positions (ie: more efficient to hire someone who can think rather than someone who can think AND a bag of meat to type on a keyboard for them). Someone who can prevent disasters by seeing and avoiding them (or just preparing for them) it worth more than someone who plows straight into them unsuspectingly.

    That's just bull. 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.

    The interviews wants to know, among other things:

    1. How the programmer fares under stress
    2. How the programmer codes rather than whomever he stole the code he's showing off in the interview codes
    3. How the programmer fares on a problem that the interview knows well enough to judge the solution off
    4. Things beyond just how good of a brainless code monkey someone is (ie: whatever job specific requirements there may be beyond knowing some random language)
  • (cs)

    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

Leave a comment on “Out of All the Possible Answers...”

Log In or post as a guest

Replying to comment #:

Log Out

« Return to Article