문제
Repeatedly divide n by 2, dropping any remainder (integer division), until it becomes 1. Count how many divisions that takes.
Implement halve_until_one(n).
Input
n: A positive integer.
Output
Return the number of divisions.
제약 조건
1 ≤ n ≤ 1,000,000,000,000
예시
예시 1
입력:
n = 20
예상 출력:
expected = 4입력:
long long n = 20;
예상 출력:
long long expected = 4;입력:
long n = 20;
예상 출력:
long expected = 4;설명
20 → 10 → 5 → 2 → 1 takes 4 divisions.
예시 2
입력:
n = 1
예상 출력:
expected = 0입력:
long long n = 1;
예상 출력:
long long expected = 0;입력:
long n = 1;
예상 출력:
long expected = 0;설명
n is already 1, so no divisions are needed.
접근 방법
먼저 스스로 풀어 본 뒤 힌트를 하나씩 열어 보세요.
힌트 1
숫자를 2로 나누며 1이 될 때까지 몇 번 줄일 수 있는지 세세요.
힌트 2
버려지는 나머지는 추적할 필요 없이 정수 나눗셈만 반복하면 됩니다.
힌트 3
값이 0이 아니라 정확히 1이 되는 지점에서 멈추세요.
예상 복잡도
시간 O(log n), 추가 공간 O(1)
참고 자료
이 문제는 CodeUtility에 맞게 수정되었습니다. 위의 설명과 제한 조건을 따르세요.