숫자를 4로 나누기 위해 삭제해야 하는 최소 자릿수

이 기사에서는 흥미로운 계산 문제인 "4로 나눌 수 있는 숫자를 만들기 위해 제거해야 하는 최소 자릿수"를 살펴보겠습니다. 이 질문은 코딩대회나 알고리즘 기반 면접에서 흔히 나오는 질문으로, 문제 해결 능력을 향상시키는 데 탁월한 연습이 됩니다.

먼저 문제 설명을 이해해 보겠습니다. 숫자가 있고 우리의 임무는 나머지 숫자가 4로 나누어질 수 있도록 최소 자릿수를 제거하는 것입니다.

개념적 이해

문제는 정수론 분야에 있습니다. 이해해야 할 중요한 사실은 숫자의 마지막 두 자리가 4로 나누어지는 경우에만 숫자가 4로 나누어진다는 것입니다. 이 사실은 우리 문제를 해결하는 데 매우 중요합니다.

알고리즘 설명

이 문제를 해결하는 알고리즘에는 다음 단계가 포함됩니다. -

• 숫자를 문자열로 변환하세요.

• 문자열 끝부터 시작하여 마지막 두 문자로 구성된 숫자가 4로 나누어지는지 확인하세요.

• 그렇다면 삭제된 자릿수를 반환하세요. 그렇지 않은 경우 마지막 문자를 제거하고 개수를 늘립니다.

• 숫자가 4로 나누어지거나 한 자리만 남을 때까지 이 작업을 반복하세요.

예

이것은 알고리즘의 C++ 구현입니다. -

으아악

출력

으아악

minRemovals 함수에서는 카운터 카운트를 0으로 초기화하여 제거된 비트 수를 추적합니다. 그런 다음 숫자(문자열)의 끝부터 반복하여 마지막 두 자리가 4로 나누어지는 숫자를 형성하는지 확인합니다. 그렇다면 개수를 반환하고, 그렇지 않으면 개수를 반환합니다. 그렇지 않은 경우 개수를 늘리고 다음 반복을 계속합니다.

main 함수는 입력 숫자를 정의하고 숫자가 4로 나누어질 수 있도록 제거할 최소 자릿수를 인쇄하는 프로그램의 진입점 역할을 합니다.

테스트 케이스 예시

번호 1351을 예로 들어보겠습니다. 마지막 두 자리(51)를 살펴보면 4로 나누어 떨어지지 않는다는 것을 알 수 있습니다. 따라서 마지막 숫자 (1)을 제거하고 숫자 135를 얻습니다. 다시 확인해 보니 마지막 두 자리(35)가 여전히 4로 나누어지지 않는 것을 알 수 있습니다. 따라서 마지막 숫자(5)를 제거하고 숫자 13을 남겨둡니다. 마지막 두 자리(13)는 4로 나누어지지 않으므로 마지막 자리(3)를 삭제합니다. 이제 4로 나누어지지 않는 숫자 1만 남았지만 더 이상 숫자를 제거할 수는 없습니다. 따라서 제거해야 할 최소 자릿수는 3입니다.

시간과 공간의 복잡성

이 알고리즘의 시간 복잡도는 O(n)입니다. 여기서 n은 숫자의 자릿수입니다. 알고리즘에서 추가 데이터 구조를 사용하지 않으므로 공간 복잡도는 O(1)입니다.

결론

이 글에서는 일반적인 컴퓨팅 문제, 즉 숫자를 4로 나누기 위해 제거해야 하는 최소 자릿수를 결정하는 문제를 살펴보겠습니다. 우리는 정수론의 주요 통찰력을 사용하여 간결한 C++ 솔루션을 개발했습니다.

위 내용은 숫자를 4로 나누기 위해 삭제해야 하는 최소 자릿수의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!