Steps to Reduce a Number to Zero

Q: 숫자를 0으로 줄이는 데 걸리는 시간 복잡도는 얼마인가요?

이 프로세스를 실행하는 데는 O(log n) 시간이 걸립니다. 적어도 두 단계마다 숫자가 절반으로 줄어들기 때문입니다. n = 2^31 - 1 인 경우 61 단계가 걸립니다. 내장 비트 명령어를 사용해 이진 자릿수를 세는 것은 O(1) 입니다.

Q: 단계 수를 구하는 공식은 무엇인가요?

n > 0 일 때 답은 n 의 이진수 길이에서 1을 뺀 값에 1 비트의 개수를 더한 값입니다. 각 1 비트마다 뺄셈을 한 번 하고, 맨 앞의 1보다 뒤에 있는 각 자릿수마다 절반으로 나누기를 한 번 합니다. n = 0 일 때 답은 0 입니다.

Q: 2^31보다 작은 수 중 어떤 수가 가장 많은 단계를 거치나요?

2^31 - 1 은 이진수로 1이 31개 있는 수입니다. 이 수는 31 번 빼기와 30 번 반으로 나누기가 필요하므로, 총 61 단계가 필요합니다. 이보다 작은 수 중에는 자릿수와 1의 개수가 동시에 이만큼인 수가 없습니다.

Q: 왜 절반으로 나누는 것이 오른쪽 시프트와 같나요?

2진수는 2의 거듭제곱들의 합입니다. 짝수를 2 로 나누면 모든 거듭제곱의 지수가 1씩 줄어들어 모든 숫자가 오른쪽으로 한 자리씩 이동하고 마지막 0 이 사라집니다. 이것이 바로 n >> 1 이 하는 일이므로, 어느 쪽으로든 절반으로 나누는 연산을 작성할 수 있습니다.

입문비트 조작 수학과 시뮬레이션

+10

음이 아닌 정수 n에서 시작해 0에 도달할 때까지 다음 규칙을 반복하세요. 수가 짝수이면 2로 나누고, 홀수이면 1을 빼세요. 규칙을 한 번 적용할 때마다 한 단계입니다. 걸리는 단계 수를 반환하세요.

함수

numberOfSteps(n: integer) → integer

ninteger: 시작 숫자
반환값integer: 숫자가 0에 도달할 때까지의 단계 수

제약 조건

0 ≤ n ≤ 2³¹ - 1

예제

입력: n = 14
출력: 6
설명: 숫자는 14 → 7 → 6 → 3 → 2 → 1 → 0이 됩니다. 절반으로 나누기 세 번과 빼기 세 번으로, 총 6단계입니다.

입력: n = 8
출력: 4
설명: 8 → 4 → 2 → 1 → 0. 2의 거듭제곱은 세 번 절반으로 나뉘고 마지막에 한 번 빼기가 필요하므로, 총 4단계입니다.

입력: n = 123
출력: 12
설명: 123는 이진수로 1111011입니다. 숫자는 7자리이고 1은 6개입니다. 1이 6개이므로 뺄셈 6회가 필요하고, 맨 앞의 1 아래에 있는 숫자 6개 때문에 반으로 나누는 과정이 6회 필요하므로 총 12단계입니다.

제출 시 숨은 테스트 +12개

후속 질문

홀수는 1씩 줄어드는 대신 1씩 커질 수도 있다고 가정해 보세요. 0에 도달하는 데 필요한 최소 단계 수는 얼마이며, 15에는 어떤 선택이 맞을까요?

힌트

하나씩 열어 보세요. 열 때마다 조금 더 알려 줍니다.

3개 중 0개 열림

풀이

이 규칙을 실행하는 것은 이미 빠릅니다. 수를 절반으로 줄일 때마다 숫자의 크기가 절반이 되므로, 2^31 - 1도 61단계만 필요합니다. 흥미로운 점은 이 규칙이 이진 숫자에 어떤 영향을 미치는지 살펴보는 것입니다. 절반으로 나누면 마지막 숫자가 사라지고, 홀수에서 1을 빼면 마지막 1이 0으로 바뀝니다. 따라서 답은 숫자의 자릿수에 1의 개수를 더한 뒤 1을 뺀 값입니다.

프로세스 실행

핵심 아이디어

문장에 적힌 대로 하면 됩니다. n이 0보다 큰 동안 짝수이면 절반으로 나누고, 홀수이면 1을 빼고, 단계를 세세요. 14의 경우 반복문은 7, 6, 3, 2, 1, 0을 방문하며, 총 여섯 단계입니다.

홀수에서 빼기를 하면 항상 짝수가 되므로, 적어도 두 단계마다 한 번은 절반으로 나누게 되어 반복문은 짧습니다. 2^31보다 작은 수는 1에 도달하기 전에 최대 30번 절반으로 나뉘며, 각 나누기 전에 한 번씩 빼고 마지막에 한 번 더 빼므로 반복문은 최대 61번 실행됩니다.

입력값 0에는 특별한 처리가 필요하지 않습니다. 반복문 조건이 즉시 거짓이 되어 답은 0입니다.

알고리즘

steps를 0으로 설정합니다.
n > 0인 동안: n이 짝수이면 n을 n / 2로 설정하고, 그렇지 않으면 n-1로 설정합니다.
매번 steps에 1을 더합니다.
steps를 반환합니다.

def numberOfSteps(n):
    steps = 0
    while n > 0:
        if n % 2 == 0:
            n //= 2
        else:
            n -= 1
        steps += 1
    return steps

이진 숫자의 개수 세기

핵심 아이디어

이진수로 과정을 살펴보세요. 14는 1110입니다. 절반으로 나누면 마지막 숫자가 사라집니다: 111. 홀수에서 1을 빼면 마지막 숫자인 1이 지워집니다: 110. 따라서 각 단계에서는 마지막 숫자를 제거하거나 끝의 1을 0으로 바꿉니다.

이제 세어 보세요. 숫자에 있는 모든 1을 한 번씩 지워야 하므로, 1 하나당 뺄셈 한 번이 필요합니다. 모든 숫자를 제거해야 하므로 맨 앞의 숫자를 제외한 각 숫자마다 절반으로 나누기를 한 번씩 해야 합니다. 1만 남았을 때는 그 숫자를 지우는 뺄셈만으로 이미 0이 되기 때문입니다. 따라서 답은 length - 1 + ones입니다. 14 = 1110의 경우 4 - 1 + 3 = 6입니다.

Java, C, C++, Go, Rust, Swift에는 두 값을 세는 내장 함수(선행 0 개수와 1 비트 개수)가 있으며, 대부분의 프로세서에서 단일 명령어로 컴파일됩니다. 다른 언어에서는 n을 이진수로 바꾸어 문자의 개수를 세거나, % 2로 각 자릿수를 읽습니다. 이 방법은 최대 31회 반복하는 루프입니다. 먼저 n = 0일 때 0을 반환하세요. 기준이 될 1비트가 없기 때문입니다.

알고리즘

n == 0이면 0을 반환합니다.
n의 이진 자릿수인 length를 구합니다.
1 비트의 개수인 ones를 구합니다.
length - 1 + ones를 반환합니다.

def numberOfSteps(n):
    if n == 0:
        return 0
    # Every bit below the leading one costs a halving,
    # and every 1 bit costs a subtraction.
    return n.bit_length() - 1 + bin(n).count("1")

함정과 경계 사례

규칙은 두 줄로 되어 있습니다. 실수는 경계 조건과 공식의 오프바이원 오류에서 발생합니다.

비트 공식에서 n = 0인 경우를 빠뜨립니다. 자릿수도 1도 없을 때 length - 1 + ones는 -1을 반환하며, 선행 0의 개수는 0일 때 정의되지 않을 수 있습니다(C의 __builtin_clz(0)).
선행 숫자를 반으로 나누는 횟수로 셉니다. 1은 뺄셈으로 0이 되므로, 8 = 1000은 5가 아니라 4 - 1 + 1 = 4번의 단계가 필요합니다.
두 단계를 하나로 합칩니다. 홀수에 n = (n-1) / 2를 쓰면 뺄셈과 나눗셈을 한 번에 수행하므로 횟수에 1이 아니라 2를 더해야 합니다. 그렇지 않으면 14는 6이 아니라 4가 됩니다.
n > 1인 동안 반복합니다. 마지막 단계에서 1이 0이 되므로 한 단계 일찍 멈춥니다. 반복문은 n이 0이 될 때까지 실행해야 합니다.

자주 묻는 질문4

숫자를 0으로 줄이는 데 걸리는 시간 복잡도는 얼마인가요?

이 프로세스를 실행하는 데는 O(log n) 시간이 걸립니다. 적어도 두 단계마다 숫자가 절반으로 줄어들기 때문입니다. n = 2^31 - 1인 경우 61단계가 걸립니다. 내장 비트 명령어를 사용해 이진 자릿수를 세는 것은 O(1)입니다.

단계 수를 구하는 공식은 무엇인가요?

n > 0일 때 답은 n의 이진수 길이에서 1을 뺀 값에 1 비트의 개수를 더한 값입니다. 각 1 비트마다 뺄셈을 한 번 하고, 맨 앞의 1보다 뒤에 있는 각 자릿수마다 절반으로 나누기를 한 번 합니다. n = 0일 때 답은 0입니다.

2^31보다 작은 수 중 어떤 수가 가장 많은 단계를 거치나요?

2^31 - 1은 이진수로 1이 31개 있는 수입니다. 이 수는 31번 빼기와 30번 반으로 나누기가 필요하므로, 총 61단계가 필요합니다. 이보다 작은 수 중에는 자릿수와 1의 개수가 동시에 이만큼인 수가 없습니다.

왜 절반으로 나누는 것이 오른쪽 시프트와 같나요?

2진수는 2의 거듭제곱들의 합입니다. 짝수를 2로 나누면 모든 거듭제곱의 지수가 1씩 줄어들어 모든 숫자가 오른쪽으로 한 자리씩 이동하고 마지막 0이 사라집니다. 이것이 바로 n >> 1이 하는 일이므로, 어느 쪽으로든 절반으로 나누는 연산을 작성할 수 있습니다.

Python

def numberOfSteps(n):
    # 여기에 코드를 작성하세요

테스트 케이스

케이스 1

케이스 2

케이스 3

입력

n = 14

기대값