GCD and LCM of an Array

Given positive integers nums, return [gcd, lcm] of all values. The GCD must be exact. Return -1 in the LCM position if the mathematical LCM exceeds 9_223_372_036_854_775_807 (the signed 64-bit maximum). Use this same result convention in Go and Python.

Function signatures

func GCDLCM(nums []int) []int64

def gcd_lcm(nums: List[int]) -> List[int]:

Examples

nums = [6,10,15]
output = [1,30]

nums = [1000000000,999999999]
output = [1,999999999000000000]

nums = [1000000000,999999999,999999997]
output = [1,-1]

The last mathematical LCM is 999999996000000003000000000, outside the result range. -1 is a sentinel, not an input to later GCD/LCM calculations.

Constraints

• 1 <= len(nums) <= 100_000
• 1 <= nums[i] <= 1_000_000_000
• No guarantee is made that the mathematical LCM fits signed 64-bit.

Hints

1. Fold Euclid's GCD over the processed prefix. The LCM uses a separate fold.
2. Divide the current LCM by its GCD with the next value before multiplying.
3. Check the reduced factor against MAX / value before multiplication.
4. Once LCM overflows it remains overflowed, but later values can still change the GCD. Continue scanning the array.