Nth Magical Number LeetCode solution in C++

1
class Solution {
2
 public:
3
  int lcm(int a, int b) // Finding the LCM of a and b
4
  {
5
    if (a == b) return a;
6
    if (a > b) {
7
      int count = 1;
8
      while (true) {
9
        if ((a * count) % b == 0) return a * count;
10
        count++;
11
      }
12
    }
13
    int count = 1;
14
    while (true) {
15
      if ((b * count) % a == 0) return b * count;
16
      count++;
17
    }
18
    return -1; // garbage value--ignore.
19
  }
20

21
  int nthMagicalNumber(int n, int a, int b) {
22
    long long int comm = lcm(a, b); // common element
23
    long long int first =
24
        (((comm * 2) - comm) / a) - 1; // no. of elements appearing before the comm multiples (a).
25
    long long int second =
26
        (((comm * 2) - comm) / b) - 1; // no. of elements appearing before the comm multiples(b).
27

28
    long long int landmark =
29
        (n / (first + second + 1)) * comm; // last common element before nth number.
30
    long long int offset =
31
        n % (first + second + 1); // how many numbers to consider after last common
32

33
    long long int p = landmark,
34
                  q = landmark; // initialisations to find the offset from the
35
                                // landmarked element
36
    long long int ans = landmark;
37
    for (int i = 1; i <= offset; i++) // forwarding offset number of times.
38
    {
39
      if (p + a < q + b) // this logic easily takes care of which elements to be
40
                         // considered for the current iteration.
41
      {
42
        ans = p + a;
43
        p = p + a;
44
      } else {
45
        ans = q + b;
46
        q = q + b;
47
      }
48
    }
49

50
    return (ans % 1000000007); // returning the answer.
51
  }
52
};
53

54
/*
55
    a and b
56
    1st step would be to find the LCM of the two numbers --> Multiples of LCM
57
   would be the common numbers in the sequential pattern. The next step would be
58
   to find the numbers of a and numbers of b appearing between the common
59
   number.
60

61
        DRY :
62

63
    4 and 6
64
    4 -> 4 8 12 16 20 24 28 32 36 40   -->
65
    6 -> 6 12 18 24 30 36 42 48 54 60  -->
66

67
    4 6 8    12     16 18 20        24 --> n/(f + s) --->  23/4 = 5 and 3
68
    5th -----> (comm * 5 = 60) ------>
69
*/