문제

풀이

public int solution(int[] arr) {
    return Arrays.stream(arr).reduce((a, b) -> a * b / gcd(a, b)).getAsInt();
}

// 최대 공약수 구하기
private int gcd(int a, int b) { 
    if (a % b == 0) return b;
    return gcd(b, a % b);
}

최대 공약수

A = a * Q

B = b * Q

A % B = r

라고 표현했을 때, 정리하다보면 결국 r 도 Q 를 갖고 있다.

따라서 A % B 가 B % r 과 같게 되고, 이 과정을 재귀적으로 반복하다가 a % b == 0이 되는 순간에서의 b 가 결국 최대공약수인 Q 가 되는 것.

최소 공배수

a * b * Q = A * B / Q