다음 문제를 해결하려고합니다.
정수 n이 주어지면 n!의 후행 0 수를 반환합니다.
참고 : 솔루션은 로그 시간 복잡성이어야합니다.
너무 느리게 거부 된 다음 코드를 제출했습니다.
public int trailingZeroes(int n) {
int result = 0;
int k = 5;
while (k <= n){
result += n / k;
k *= 5;
}
return result;
}
하지만 변수 k를 long으로 변경하면 충분히 빠릅니다.
int 대신 k as long을 선언하면 왜 더 빠릅니까? (내가 올바르게 이해하면 반대가 일어나야한다고 말하는 이 질문 을 읽었습니다. )
@Tunaki의 의견은 아마도 돈에 대한 것입니다. 귀하의 경우 n보다 큰 Integer.MAX_VALUE / 5를 들어, 다음이 가능합니다 k보다 값이 큰에 도달 Integer.MAX_VALUE / 5한 후 5 곱한 후, 그것은 오버 플로우 및 프로그램이 종료하지 않도록, 다시 소수가된다.
반면에 k길이가 긴 경우 값이보다 큰지 여부는 중요하지 않습니다 Integer.MAX_VALUE / 5. 그것이 int이고 int가 충분히 가까운 값에 도달하지 Long.MAX_VALUE / 5않기 때문에 보장되는 것 보다 작 으면 n오버플로가 발생하지 않습니다.
이 기사는 인터넷에서 수집됩니다. 재 인쇄 할 때 출처를 알려주십시오.
침해가 발생한 경우 연락 주시기 바랍니다[email protected] 삭제
몇 마디 만하겠습니다