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).

A:
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

14 comments:

  1. such an idiotic approach, clearly this guy has no idea about math, check what is the better way to find GCD and then u'll get LCM directly

    ReplyDelete
  2. LCM = (m*n)/gcd(m,n)

    Find gcd(m,n) in log(n) time by Euclid's Method.

    ReplyDelete
  3. Thanks for the approach ... It works

    ReplyDelete
  4. This is a terrible idea, it would require a list of primes. LCM(a,b) = (a*b) / GCD(a,b) .

    ReplyDelete
  5. This would require a list of primes. Better to use LCM(a,b) = (a*b) / GCD(a,b)

    ReplyDelete
  6. Approach is correct.

    ReplyDelete
  7. best way to get gcd is euclidean formula..assuming m>n gcd(m,n){
    if n==0 return m;
    return gcd(n,m%n);}

    nw gcd*lcm=m*n

    ReplyDelete
  8. It's a very complex approach for this kind of problem. Keep it simple :).

    Given n and m, what is their LCM ?
    - Iterate over each number between n and n*m with a step of n (every multiple of a)
    - If the current number x is a multiple of b, then stop, you found it ! (It is the first multiple of b that is also a multiple of a)

    Regards.

    ReplyDelete
  9. There's a much much much simpler approach using basic a really basic algorithm:


    - Foreach x between m and m*n with step n
    --- If x modulo n == 0
    ----- break; //x is the least common multiple

    ReplyDelete
  10. I've been studying your algorithm for 20 minutes and its just too confusing. I don't think it would be easy to come up with code that "find[s] the largest a and b such that p^a \ m and p^b \n", I'm also not convinced that that's what you're looking for. I'm pretty sure that algorithm doesn't work in any case, please provide an example with a trace if it does work.

    I propose a different (read: simpler) algorithm:

    public int LCM(int m, int n){
    if(m>n){ //ensure n>m
    int t = m;
    m = n;
    n = t;
    }
    int x = n;
    while(x%m != 0) //loop ends when x divided by m gives 0 as the remainder
    x+=n;
    return x;
    }

    The idea is to go through multiples of one number until you find one that is divisible by the other number. Sorting the given numbers first ensures that the algorithm only goes through the loop the fewest number of times necessary to produce the correct answer.

    ReplyDelete
  11. #include
    main(){
    int a,b,min,gcd,i,lcm;
    scanf("%d%d",&a,&b);
    min=a>b?b:a;
    for(i=min;i>=1;i--)
    if(a%i==0 && b%i==0) break;
    gcd=i;
    printf("gcd %d",gcd);
    lcm=(a/gcd)*(b/gcd);
    printf("lcm,, %d",lcm);
    return 0;
    }

    ReplyDelete
  12. @Original poster - Uh... check for invalid inputs, and then return n*m - prime numbers have nothing to do with the proper solution. You have either posed an incomplete question, answered something completely different, or have no idea what you're doing.

    ReplyDelete
  13. It's look like GCD(http://en.wikipedia.org/wiki/Greatest_common_divisor) mathematics classic problem :
    /**
    * Owner : Ghodrat Naderi
    * E-Mail: Naderi.ghodrat@gmail.com
    * Date : 7/19/12
    * Time : 10:25 PM
    * IDE : IntelliJ IDEA 11
    */
    public class Gcd
    {
    public static void main(String[] args)
    {
    int a = 180;
    int b = 48;
    System.out.println("GCD(" + a + "," + b + ")=" + gcd(a, b));
    }

    private static int gcd(int a, int b)
    {
    if (a == 0)
    return b;
    if (b == 0)
    return a;
    if (a == b)
    return a;
    if (a > b)
    return gcd(b, a % b);
    else
    return gcd(a, b % a);

    }
    }

    ReplyDelete
  14. hi...this is very great post..we can improve our skills from this post..thanks..job interview tips

    ReplyDelete