CODEWITHSUNDEEP
algorithm
virmis_007
virmis_007

Reputation: 173

nth number of a list of multiples of two numbers

Came across this question in an Amazon hiring challenge a few months back.
Given two numbers a and b and the list of their multiples in ascending order, find the nth multiple.

For example if a = 4 , b = 6 and n = 6 then answer is 18 since the list is 4 6 8 12 16 18 20 24 28 30....

Here is the approach I used:

  1. Choose the smaller of a and b. Assign it to small. Assign the other one to big.

  2. Generate the list (as shown above) of multiples of both a and b upto small*n, since the required answer couldn't be greater than this.

  3. Create a pointer to the last number in this list.

  4. Move back this pointer by the number of multiples the bigger number has till small*n ( simply retract the pointer by (small * n)/big).

  5. Move the pointer forward by the number of least common multiples of both a and b have till small * n. This is the required answer.

This approach worked fine on small test cases but TLEd on bigger ones.

Please suggest a lesser time-complex approach. And for some reason, Mathjax ain't working in any of my browsers.

Upvotes: 4

Views: 731

Answers (2)

גלעד ברקן
גלעד ברקן

Reputation: 23945

We can have a simple binary search, considering that the number of multiples up to an arbitrary natural, n, is floor(n / a) + floor(n / b) - floor(n / lcm(a, b)). Then subtract the result by the smaller of result mod a or result mod b.

JavaScript code:

function gcd(a,b){
  while (b > 0)
    [a, b] = [b, a % b];

  return a;
}

function lcm(a, b){
  return a * b / gcd(a, b);
}

function countMul(a, b, lcmAB, n){
  return ~~(n / a) + ~~(n / b) - ~~(n / lcmAB);
}

function nthMul(a, b, n){
  let low = Math.min(a,b);
  let high = n * Math.min(a,b);
  let mid = ~~((low + high) / 2);
  let lcmAB = lcm(a, b);
  
  while (countMul(a, b, lcmAB, mid) != n){
    if (countMul(a, b, lcmAB, mid) > n)
      high = mid;
    else
      low = mid;
    
    mid = ~~((low + high) / 2);
  }
  
  return mid - Math.min(mid % a, mid % b);
}

console.log(nthMul(4,6,6));

Upvotes: 2

MBo
MBo

Reputation: 80267

As noticed, find L=LCM(a,b) (here 12)
Also calculate la = LCM/a, lb = LCM/b (here 3,2)
Note that L stands at F = la + lb - 1-th place in the row, and k-th multiple of LCM stands at k * F-th place of sequence (here k*4)
So you can easily find:
-interval where n-th member is: idx = n div F (here 6 div 4 = 1 starting from 0)
-place in this interval: p = div mod F (here 6 mod 4 = 2 starting from 0)

Now you have to find p-th item in the range 0..LCM - 1. Note that you don't need to build a list (possible approach - binary search)

Upvotes: 3

Related Questions