LCM of an Array with Modulo

Problem Description:

Find LCM of N numbers, with modulo M, where for this problem statement M is 1e9 + 7.

Sample Input:

A: [13, 412, 56, 70, 333]

Sample Output:

124848360

Solution Approach:

One thing to notice is that you can not take modulo in between the LCM operation.

For example:

Case 1: When you take modulo in between the LCM operation. 

LCM(12, 3, 8) % 10 
LCM( LCM(12,3) % 10, 8 ) % 10
LCM( 12 % 10, 8) % 10
LCM( 2, 8 ) % 10
8

Case 2:

LCM(12,3,8) % 10
24 % 10
4

So 4 is the correct answer, that's why we can not approach this problem as suggested by Case 1.

So, to solve it elegantly, we can use prime factorization, for example,

A: [12, 3, 8]

12: 2² * 3¹
3: 3¹
8: 2³

Take max power of each prime number, then multiply it, you will get 2³ * 3¹ = 24

So while multiplying those numbers you can use modulo now.

Sample IO Explanation:

A: [13, 412, 56, 70, 333]
13: 13¹
412: 2² x 103¹
56: 2³ x 7¹
70: 2¹ x 5¹ x 7¹
333: 3² x 37¹

So, LCM = (2³ x 3² x 5¹ x 7¹ x 13¹ x 37¹ x 103¹) % (1e9 + 7) = 124848360

Time Complexity: O(NlogN)

Solution in CPP: