Cracking the Coding Interview: Fourth Edition (308 page e-book / PDF)
Delivered instantly as a PDF via email. For Software Engineers & SDETs
  • 150 programming interview questions and answers
  • 5 proven approaches to crack algorithm questions
  • 10 mistakes candidates make, and how to avoid them.
  • How to prepare for technical and behavioral questions without wasting your time!
"The BEST book for acing your interview. It helped me land my Microsoft job, and it was worth every penny!" - Ravi (Accepted at Microsoft, Amazon and Facebook) 30 Day Money Back Guarantee: Don't love the book? We'll give you your money back! More Info

Friday, September 30, 2011

Common multiple

Q: Given two numbers m and n, write a method to return the first number r that is
divisible by both (e.g., the least common multiple).

The Approach:
What does it mean for r to be divisible by m and n? It means that all the primes in m must go into r, and all primes in n must be in r. What if m and n have primes in common?

For example, if m is divisible by 3^5 and n is divisible by 3^7, what does this mean about r? It means r must be divisible by 3^7.

The Rule: For each prime p such that p^a \ m (e.g., m is divisible by p^a) and p^b \ n, r must be divisible by p^max(a, b)

The Algorithm:
Define q to be 1.
for each prime number p less than m and n:
find the largest a and b such that p^a \ m and p^b \ n
let q = q * p^max(a, b)
return q