Steps to Reduce a Number to Zero

Q: 수를 0으로 줄이는 데 걸리는 시간 복잡도는 무엇인가요?

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

Q: 2^31보다 작은 수 중에서 단계가 가장 많이 필요한 수는 무엇인가요?

이는 이진수로 1이 31개인 수입니다. 뺄셈이 31 번, 2로 나누기가 30 번 필요하므로 총 61 단계입니다. 이보다 작은 수 중에는 자릿수와 1의 개수가 모두 이만큼인 수가 없습니다.

Q: 왜 2로 나누는 것이 오른쪽 시프트와 같은가요?

2진수는 2의 거듭제곱들의 합입니다. 짝수를 2 로 나누면 모든 거듭제곱의 차수가 하나씩 낮아져 모든 숫자가 오른쪽으로 한 자리 이동하고 마지막 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은 2진수로 1111011입니다. 숫자는 7자리이고 1은 6개입니다. 1이 6개이므로 뺄셈에 6단계가 들고, 맨 앞의 1 아래에 있는 숫자 6개를 반으로 나누는 데 6단계가 들어 총 12단계입니다.

후속 질문

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

힌트

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

3개 중 0개 열림

풀이

2진수에서는 절반으로 나누면 마지막 자릿수가 없어지고, 홀수에서 1을 빼면 마지막 1이 0으로 바뀝니다. 따라서 n > 0일 때 답은 2진수 자릿수와 1의 개수를 더한 값에서 1을 뺀 것입니다. 규칙을 직접 적용해도 빠릅니다. 최대 61단계입니다.

프로세스를 실행합니다

핵심 아이디어

규칙을 실행하고 단계 수를 세어 보세요. 14의 경우 루프는 7, 6, 3, 2, 1, 0을 방문합니다. 총 6단계입니다.

빼기를 하면 항상 홀수가 짝수가 되므로, 적어도 두 단계마다 한 번은 절반으로 줄어듭니다. 2^31보다 작은 수는 1에 도달하기 전에 최대 30번 절반으로 줄어듭니다. 절반으로 줄일 때마다 그 전에 빼기를 한 번 하고 마지막에 한 번 더 빼므로, 루프는 최대 61번 실행됩니다. n = 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

이진 숫자 세기

핵심 아이디어

각 단계에서는 마지막 이진 숫자를 제거하거나 끝의 1을 0으로 바꿉니다. 14는 1110입니다. 반으로 나누면 111이 되고, 111에서 빼면 110이 됩니다. 모든 1은 한 번씩 지워야 하므로, 1 하나당 뺄셈이 한 번 필요합니다. 맨 앞의 숫자를 제외한 모든 숫자는 반으로 나누어 한 번씩 제거해야 합니다. 1만 남았을 때는 빼기만 해도 이미 0이 되기 때문입니다. 따라서 답은 length - 1 + ones이며, 14의 경우 4 - 1 + 3 = 6입니다.

Java, C, C++, Go, Rust, Swift에는 두 가지 개수(선행 0과 설정된 비트)를 구하는 내장 기능이 있으며, 대부분의 프로세서에서 단일 명령어로 컴파일됩니다. 다른 언어에서는 최대 31회 반복하는 루프에서 % 2를 사용해 숫자를 읽습니다. 먼저 n = 0인 경우를 처리하세요. 공식에 기준이 되는 1 비트가 없기 때문입니다.

알고리즘

n == 0이면 0을 반환합니다.
length, 즉 n의 이진 자릿수를 구합니다.
ones, 즉 1 비트의 개수를 구합니다.
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을 빼먹는 경우. length - 1 + ones는 -1이 되고, 선행 0의 개수가 0이면 정의되지 않을 수 있습니다(C의 __builtin_clz(0) 참조).
선행 숫자에 대해 절반으로 줄이는 횟수를 세는 경우. 뺄셈으로 1은 0이 되므로, 8 = 1000은 5단계가 아니라 4 - 1 + 1 = 4단계가 걸립니다.
홀수에 n = (n-1) / 2를 쓰고 한 단계를 세는 경우. 이 줄은 두 단계를 수행하므로, 14의 결과는 6이 아니라 4가 됩니다.
n > 1인 동안 반복하는 경우. 이렇게 하면 1을 0으로 바꾸는 마지막 단계 전에 멈춥니다.

자주 묻는 질문3

수를 0으로 줄이는 데 걸리는 시간 복잡도는 무엇인가요?

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

2^31보다 작은 수 중에서 단계가 가장 많이 필요한 수는 무엇인가요?

이는 이진수로 1이 31개인 수입니다. 뺄셈이 31번, 2로 나누기가 30번 필요하므로 총 61단계입니다. 이보다 작은 수 중에는 자릿수와 1의 개수가 모두 이만큼인 수가 없습니다.

왜 2로 나누는 것이 오른쪽 시프트와 같은가요?

2진수는 2의 거듭제곱들의 합입니다. 짝수를 2로 나누면 모든 거듭제곱의 차수가 하나씩 낮아져 모든 숫자가 오른쪽으로 한 자리 이동하고 마지막 0이 사라집니다. 이것이 n >> 1이 하는 일이므로, 절반으로 나누는 연산은 두 방식 중 어느 쪽으로든 쓸 수 있습니다.

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

테스트 #1

테스트 #2

테스트 #3

인자

n = 14

예상 출력