시간/공간 복잡성 감소. 프로그래밍 경연

Question

스킬 테스트 시스템 중 하나에서 다음 프로그래밍 문제가 발견되었습니다.

양수 N이 주어집니다. 숫자의 시퀀스 [0, 1, ..., N]을 고려하십시오. 이 숫자의 십진수 표현의 총 0은 얼마입니까?

N은 매우 클 수 있습니다. 따라서 N의 10 진수 표현을 포함하는 길이가 L 인 비어 있지 않은 문자열 S의 형태로 제공됩니다. S에는 선행 0이 없습니다.

함수를 적는다

어떤 양의 정수 N의 진수 표현 문자열 S, 주어진 숫자 [0, 1의 진수 표현으로 0의 수를 반환

int number_of_zeros(char *S); 


int number_of_zeros(const string &S); 

, ..., N]. 결과가 1,410,000,016을 초과하는 경우 함수는 결과의 나누기에서 나머지를 1,410,000,017만큼 반환해야합니다.

* L is an integer within the range [1..10,000]; 
    * string S consists only of digits (0-9); 
    * string S contains no leading zeros. 

복잡성 : 그

예를 들어, S에 대해 = "100"기능 (12)을 돌려 및 S에 대해 = "219"는 42

가 가정 돌려

* expected worst-case time complexity is O(L); 
    * expected worst-case space complexity is O(L) (not counting the storage required for input arguments). 

나는 그것을 풀려고했지만 함수를 작성했지만 실행 시간의 복잡성은 O (L)보다 더 복잡하다. 누군가 알고리즘을 제공 할 수 있을까? 의사 코드 또는 설명)?

성공 사례!

Answer 1

이 문제는 재귀의 장점 중 좋은 예입니다. 간단한 기본 경우를 고려하십시오. 1에서 1까지의 숫자는 정확히 0이됩니다.

1에서 N (말 x)까지의 숫자가 0 일 때 1에서 N * 10까지의 숫자를 9 * x + log10 (N * 10)으로 계산할 수 있습니다. 인수는 간단합니다. 숫자 1, 2, ... 3에 대해 동일한 수의 0으로 9 개의 블록이 필요하고 숫자 N * 10은 10000 ...으로 작성됩니다.

이 재귀는 10의 모든 제곱근에 유효합니다. 임의의 N에 대한 재귀는 숫자를 구성하는 10의 제곱으로 숫자를 나눌 때 훨씬 더 어렵지 않습니다.

Answer 2

상한선이 10000이고 기술적으로 시간 공간 복잡성 감소 대회이므로 제출 코드에서 가능한 모든 답을 미리 계산하기 만하면됩니다. 이것은 매우 비효율적 인 메모리라는 것을 알 수 있지만, 어떤 조회 값이 '0'에서 9 자리 이상 떨어져있는 상황이 결코 없다는 사실을 알면 사전을 사용하여 많은 양의 메모리를 절약 할 수 있습니다.

zeros.py는 (L에 선형 시간이기는하지만, 실제의 코드를 생성한다)

def zeros(n): 
     l = str(n) 
     return l.count("0") 

total = 0 
d = {} 
for i in xrange(10001): 
     delta = zeros(i) 
     if (delta>0): 
       total += delta 
       d[i] = total 

print len(d) 
print 
print "d = " + str(d) 
print "N = int(raw_input())" 
print "while (N not in d):" 
print "\t N-=1" 
print "print d[N]" 

가 (31ms 단위)이 (32킬로바이트) 파일을 생성 http://paste.pocoo.org/show/504589/

런타임 ~ 상각 O를 (1)

스페이스 ~ L = [0..10000]에 대한 0의 밀도는 2621 ~ 26.21 %입니다.나는 제로의 분포가 크게 증가 할 것이라고 생각하지 않지만, 그것의 밀도는 O (L)에 의해 확실히 한정됩니다.