top of page

### Looking to master object-oriented and system design for tech interviews or career growth?

• Improve your system design and machine coding skills.

• Study with our helpful resources.

**We're in beta mode and would love to hear your feedback.

Search

# 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`