모든 챌린지
쉬움 1명 해결 정답률 14.3%

Least Common Multiple

Find the smallest positive number divisible by both values.

배우게 될 내용

  • Compute the LCM from the GCD
  • Avoid overflow by dividing before multiplying
  • Reuse one function inside another

문제

번역본 보기

Return the least common multiple of a and b, the smallest positive number that both divide. lcm(a, b) = a / gcd(a, b) × b.

Implement lcm(a, b).

Input

a: The first positive number. b: The second positive number.

Output

Return lcm(a, b).

제약 조건

1 ≤ a, b ≤ 1,000,000,000

예시

예시 1
입력:
a = 4
b = 6

예상 출력:
expected = 12
입력:
long long a = 4;
long long b = 6;

예상 출력:
long long expected = 12;
입력:
long a = 4;
long b = 6;

예상 출력:
long expected = 12;

설명

Multiples of 4: 4, 8, 12…; multiples of 6: 6, 12…; the first common one is 12.

예시 2
입력:
a = 7
b = 7

예상 출력:
expected = 7
입력:
long long a = 7;
long long b = 7;

예상 출력:
long long expected = 7;
입력:
long a = 7;
long b = 7;

예상 출력:
long expected = 7;

설명

A number's LCM with itself is the number: 7.

접근 방법

먼저 스스로 풀어 본 뒤 힌트를 하나씩 열어 보세요.

힌트 1

Use the relationship between gcd and lcm instead of searching for multiples.

힌트 2

Compute the gcd first, then combine the two numbers carefully.

힌트 3

Divide before multiplying to reduce overflow risk, even with large inputs.

예상 복잡도

O(log min(a, b)) time, O(1) extra space

참고 자료

이 문제는 CodeUtility에 맞게 수정되었습니다. 위의 설명과 제한 조건을 따르세요.

코더마다 가장 좋은 통과 풀이입니다. 더 빠르고, 메모리를 덜 쓰고, 평가가 좋은 풀이가 위에 옵니다.

# 코더 언어 시간 메모리 AI 평가 풀이
1 HJhettory Jurash Python 1,017 ms - 4/5 코드 보기

다른 사람의 풀이 보기

커뮤니티 솔루션

스포일러: 아래에 1개 전체 솔루션 있음 먼저 직접 풀어보세요. 다른 개발자의 코드와 AI 리뷰도 참고할 수 있습니다. 로그인하고 문제를 풀면 토론에 참여할 수 있습니다.