• Ryan (unregistered)

    Actually, since the answer is a constant, there's no use in calculating it more than once.

    const int ANSWER_TO_POINTLESS_QUESTION = 232792560;

  • Brett_cgb (unregistered)

    There are two good answers that would work:

    1. 0
    2. 232,792,560 (or any integer multiple of this) 22223357111317*19 (all primes below 20, and a few extra 2's and 3's)
  • Neenjacoder (unregistered) in reply to Anonymous
    Anonymous:
    I think TRWTF is that the guy started his program from 1, instead of 2520 when the problem clearly states:

    "2520 is the smallest number that can be divided by each of the numbers from 1 to 10 without any remainder."

    Obviously, when considering 1-20, the smallest number is not going to be anything smaller than 2520 ><

    Another shortcut (of many) is that the result for LCM(1..20) will be a multiple of LCM(1..10).

  • Thomas Clarke (unregistered) 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, which the applicant clearly didn't have.
    He has basic programming skill. His maths/optimization skills may suck, but his *programming* is at least competent enough to produce a working section of code that produces a correct answer within a matter of seconds.
  • Deyan (unregistered) in reply to mcwyrm

    I think not - we are looking for the LCM. This would not give us that number. It would multiply 2019181716 which is already wrong(it contains 2 to the power of 7 and the LCM has 2 to the power of 4)

  • Andrew (unregistered) in reply to jwenting

    Another 10 years of PHP experience and he won't even be able to write Hello World. :)

  • noname (unregistered)

    if he can write that code with 10 years of experience, i can not imagine what he would write had he say 20 years of such experience

  • Craig Landrum (unregistered)

    When I interview, I never test. Testing people is pretty meaningless in the pressurized interview atmosphere, since it has little to do with real work. Because I may eventually have to work with whoever I hire, part of my job as an interviewer is to also sell myself to them as someone they would value as a colleague - not someone they have to fear. I much prefer to ask potential candidates to bring me samples of whatever they consider to be their most interesting work and be prepared to discuss what they found interesting about the task. That way, not only do I get a decent reading on their skill level, I also get and idea about how passionate they will be on the job.

  • Edgar (unregistered)

    Well, at least he knew that every problem in computer science can be solved by a search algorithm.

  • Andrae Muys (unregistered) in reply to Anonymous

    Actually as a generic algorithm it's straight forward. You only have to inductively apply the insight you already demonstrate. I don't know PHP, so I'll just use pseudo-code:

    leastCommonMultiple :: int -> long leastCommonMultiple n = fold * 1 (minSpanningPrimes n)

    minSpanningPrimes :: int -> List int minSpanningPrimes n where n < 2 = [] minSpanningPrimes n = generateSPrimes n (minSpanningPrimes (n - 1)) where generateSPrimes x primeList = foldl condDiv x primeList where condDiv n d where n % d == 0 = n / d condDiv n d where n % d != 0 = n

    My initial answer in response to the question was:

    leastCommonMultiple :: int -> long leastCommonMultiple n = fold * 1 (minSpanningPrimes n)

    minSpanningPrimes n where n == 20 = [2,2,2,2,3,3,5,7,11,13,17,19] minSpanningPrimes n where n != 20 = throw error "Calculating spanning Primes unimplemented"

    As an interview question it is fine. You really are testing if the person can write code at all (which the WTF answer satisfied perfectly well) - and also how they approach problem solving. Do they think iteratively or inductively? If they take a brute-force approach, do they show any discomfort at it? Do they consider doing some manual work offline to simplify the online calcuation? Do they (as in my solution), include indications of how a brute-force/manual solution might be generalised/improved?

    Anyone commenting on this question as if it was a simple pass/fail simply doesn't have the experience necessary to be considered for an interviewing position. That this is a question likely to be outside the comfortable, day-to-day experience, of an applicant is actually a good thing.

  • Calling myself Anonymous (unregistered) in reply to Max

    Yeah, there is a smarter way. Faster, anyway. This particular algorithm takes forever. Sure, it's shorter to write out when not done stupidly (10 lines of Python for the naive algorithm, 19 for the one I'm about to show you), but it takes forever: I'm running the version in the post above while I write this. The algorithm I've given here runs in much faster time, and can be readily generalized.

    The set of prime factors for a number divisible by all numbers n such that 2 <= n <= 20 will contain only the prime numbers <= 20, illud est 2, 3, 5, 7, 11, 13, 17, and 19.

    In addition, we shall need the highest power of each of those numbers that is less than 20. Since 5 ^ 2 == 25, we're only looking at powers of 2 and 3. The highest power of 2 < 20 is 16 (2^4), and the highest power of 3 < 30 is 9. Thus, we need to do some multiplication: 16 * 9 * 5 * 7 * 11 * 13 * 17 * 19 = 232,792,560, the smallest number divisible by all integers between 1 and 20, inclusive.

  • nizidramaniyt (unregistered) in reply to ideo

    I thought so too, but it turned out that 2520 wasn't divisible by 16. I wonder what the right way to do it is...

  • Daniel (unregistered)

    I don't know how can anyone call haskell pseudo-code. Pseudo-code is supposed to be readable and english-like!

    Anyway, I don't like any answer here. I lie. I like the suggestion of using lcm(1..10) as an increment, because it was given, and I like the suggestions that use lcm. The programmer yielding the faster, cleaner and less error prone code will be the one using lcm from a library.

    That said, my solution:

    #!/usr/bin/perl

    our @primes; our @factors;

    foreach $number (2..$ARGV[0]) { if(grep {$number % $_ == 0} (@primes)) { @factors = map { ($number%($primes[$]$factors[$_]) == 0) ? $primes[$_]$factors[$] : $factors[$_] } (0..$#factors); } else { push @primes, $number; push @factors, $number; } }

    print eval join("*", @factors), "\n";

  • Anonymous Coward (unregistered)
    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?

    Well, to make it divisible by all evens from 12 thru 20 (in addition to all ints from 1 thru ten), just double it. Then you have to factor the remaining odd composites: 15=3×5 (so if it's a multiple of both those numbers, which it is, it should be a multiple of 15) No other odd composites remain! Now all we have left to do is account for intervening primes, and the only way to do that is to multiply by them. Thus, my answer would be: 2520×2×11×13×17×19=232,792,560 (digit separator:',') see also http://www.google.com/search?q=2520%C3%972%C3%9711%C3%9713%C3%9717%C3%9719

    Now maybe I missed a trick there and it isn't the smallest, but it's the smallest you can get at without reaching for any electronic device other than a 4 function calculator at the end (or Google :), and it's well thought out. In other words, I did this without Perl, Python, Java, C++, or anything of that nature.

  • Anonymous Coward (unregistered) in reply to Anonymous Coward

    self reply, for those with encoding problems: The char I used is the unicode multiplication sign or U+00D7. It's supposed to look vaguely like 'x'

  • Mr. Mista (unregistered) 
    for (int i = 20; i < Integer.MAX_VALUE - 20; i += 20) {
    for (int j = 19; j > 0 && i % j == 0; j--) {
        if (j == 1) {
            System.out.println(i);
            return;
        }
    }
}

    Brute force Java.

  • Wibb (unregistered) in reply to Addison

    If 10,000-100,000 requests come through for this information and it's not all being memoized and cached, yes, this is a problem.

    If you figure this out brute-force and make the answer a static result in a lookup table, no harm is done.

  • Nic (unregistered) in reply to complete looney

    int isprime(int n){ int i; for(i = 2; i < n; i++) if( n % i == 0 ) return 0; return 1; }

    int main(int argc, char **argv){ int *primes = NULL; int count = 0;

    primes = (int*)malloc(sizeof(int)*20);
primes[0] = 2;
primes[1] = 3;

count = 2;
unsigned long product = 6;
int i =0;
//generate primes 1-20
//product = primes multiplied

for(i = 4; i <= 20; i++)
	if( isprime(i) ){
		printf("Number %d is prime\n",i);
		product *= i;
		primes[count++] = i;	
	}

int multiply = 0;	

int rem = product;

while(1){
	multiply++;
	product *= multiply;
	for(i = 1; i <= 20; i++)
		if(product %i) {
			break;	
		}

	if(product %i ) continue;
	else break;
}
	
printf("Result is %d\n",product);

free(primes);
return 0;

    }

  • hoschi (unregistered) in reply to Ren
    Ren:
    #!/usr/bin/perl

    End result:

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

    In an interview, I'd solve the problem 10 times out of 10 like this. Why? It's easy, readable and reliable.

    And its wrong. The result being. $ bc 23257231113217 12252240 ^D $ echo WTF

  • (cs) in reply to hoschi
    hoschi:
    Ren:
    #!/usr/bin/perl

    End result:

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

    In an interview, I'd solve the problem 10 times out of 10 like this. Why? It's easy, readable and reliable.

    And its wrong. The result being. $ bc 23257231113217 12252240 ^D $ echo WTF

    And why do you discriminate against 19?
  • al (unregistered) in reply to mcwyrm

    except your solution would be wrong.

    It will not find the lowest common multiple. Just a multiple.

  • mrjackinc (unregistered)

    Well this guy... lacks not only programming skills but common sense... you can find this answer without writing one line of code, using the Windows Calculator and write: 23257231113217*19

    I wonder if this is a more efficient solution XD...

    Cheers

  • Felix (unregistered)

    I haven't found this approach while looking through the comments:

        Public Function prob_5(ByVal n As Integer) As Long
        Dim value As Long = 6 
        Dim tmp As Integer
        For i As Integer = 4 To n
            If Not value Mod i = 0 Then
                tmp = (value Mod i)
                If i Mod tmp = 0 Then
                    value = value * (i / (tmp))
                Else
                    value = value * i
                End If
            End If
        Next
        Return value
    End Function

    -Felix

  • Psi (unregistered) in reply to Brian W

    increment x by 20 instead of 1, 20 times less loopage

  • Psi (unregistered) 
        $number = 0;
    $found = false;
    
    while (!$found)
    {
        $number += 20;
        $found = true;
        
        for ($i = 20; $i >= 1; $i--)
        {
            if ($number % $i)
            {
                $found = false;
                break;
            }
        }
    }
    
    echo $number; // 232792560
  • DandyDanD (unregistered)

    Surely there is a better way! (Not sure if this qualifies as PHP, though...)

    n = 20;
x = 1;
for(i = 2; i <= n; i = i+1) {
  if(floor((log(i) - log(x)) <> (log(i) - log(x)) {
    for(j = 2; j <= i; j = j+1) {
      if(floor((log(i) - log(j)) == (log(i) - log(j)) {
        if(floor((log(x) - log(j)) == (log(x) - log(j)) {
          x = x*j;
          i = i/j;
          j = j-1;
        }
      }
    }
  }
}
print x
  • jerk_programmer (unregistered) in reply to snoofle

    My best guess, tbh, is that if you're terrible at solving 'puzzles' such as this - extremely simple 'puzzles' , then you're terrible at solving any 'business problems', even fairly simple ones. Business problems are ill defined enough and the complexity is not ranked in any way other than by yourself - and this lets the Dunning-Kruger effect protect your ego.

  • robcozzens (unregistered) in reply to mcwyrm

    Very elegant, but it doesn't produce the correct answer.

  • Poochy.EXE (unregistered)

    I must ask: Would you consider it a good, bad, or neutral thing if a candidate got this question and said "Just gimme a pencil, paper, and a calculator; I don't need a full-fledged computer for this" and proceeded to get a perfectly good solution in a couple minutes that way?

  • Hung Tran (unregistered)

    I would've done it this way. Sure, it may not be the fastest, but it's the easiest and most obvious solution that I immediately thought of.

    //warning. Java below

    class test{
	public static void main(String[] args){
		find_LCM(1,20);
	}
	
	public static void find_LCM(int begin, int end){
		loop:
		for (int i = 1; ; i++)
			for (int j = begin; j<=end; j++){
				if (i%j!=0)
					continue loop;
				if (j==end && i%j==0){
					System.out.println("Result is: " + i);
					break loop;
				}
			}
	}
}

    Anything wrong with that?

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