Oto odpowiedź, która działa ze stałą pamięcią, kosztem procesora. To nie jest dobra odpowiedź w kontekście pierwotnego pytania (tj. Odpowiedzi podczas wywiadu). Ale jeśli wywiad trwa 24 godziny, to nie jest tak źle. ;)
Chodzi o to, że jeśli mam n, która jest poprawną odpowiedzią, to następną w sekwencji będzie n razy potęga dwóch, podzielona przez potęgę 5. Albo n razy potęga 5, podzielona przez potęga dwóch. Pod warunkiem, że dzieli się równomiernie. (... lub dzielnikiem może być 1;), w którym to przypadku pomnożymy przez 2 lub 5)
Na przykład, aby przejść z 625 do 640, należy pomnożyć przez 5 ** 4/2 ** 7. Lub, bardziej ogólnie, pomnożyć przez pewną wartość 2 ** m * 5 ** n
dla pewnego m, n, gdzie jeden jest dodatni, a drugi ujemny lub zero, a mnożnik dzieli liczbę równomiernie.
Teraz trudną częścią jest znalezienie mnożnika. Wiemy jednak: a) dzielnik musi dzielić liczbę równomiernie, b) mnożnik musi być większy niż jeden (liczby ciągle rosną), c) jeśli wybierzemy najniższy mnożnik większy niż 1 (tj. 1 <f <wszystkie pozostałe f ), to z pewnością będzie nasz następny krok. Kolejny krok będzie najniższym krokiem.
Paskudną częścią jest znalezienie wartości m, n. Możliwości są tylko log (n), ponieważ jest tylko tyle 2 lub 5 do zrezygnowania, ale musiałem dodać współczynnik -1 do +1 jako niechlujny sposób radzenia sobie z zaokrągleniem. Musimy więc tylko iterować przez O (log (n)) na każdym kroku. Więc ogólnie jest to O (n log (n)).
Dobrą wiadomością jest to, że ponieważ wymaga ona wartości i znajduje następną wartość, możesz zacząć w dowolnym miejscu w sekwencji. Jeśli więc chcesz mieć następny po 1 miliardie, możesz go po prostu znaleźć, wykonując iteracje 2/5 lub 5/2 i wybierając najmniejszy mnożnik większy niż 1.
(pyton)
MAX = 30
F = - math.log(2) / math.log(5)
def val(i, j):
return 2 ** i * 5 ** j
def best(i, j):
f = 100
m = 0
n = 0
max_i = (int)(math.log(val(i, j)) / math.log(2) + 1) if i + j else 1
#print((val(i, j), max_i, x))
for mm in range(-i, max_i + 1):
for rr in {-1, 0, 1}:
nn = (int)(mm * F + rr)
if nn < -j: continue
ff = val(mm, nn)
#print(' ' + str((ff, mm, nn, rr)))
if ff > 1 and ff < f:
f = ff
m = mm
n = nn
return m, n
def detSeq():
i = 0
j = 0
got = [val(i, j)]
while len(got) < MAX:
m, n = best(i, j)
i += m
j += n
got.append(val(i, j))
#print('* ' + str((val(i, j), m, n)))
#print('- ' + str((v, i, j)))
return got
Zweryfikowałem pierwsze 10 000 liczb, które to generuje, względem pierwszych 10 000 wygenerowanych przez posortowane rozwiązanie listy, i działa to przynajmniej tak daleko.
BTW, następny po bilionie wydaje się być 1 024 000 000 000.
...
Hm Mogę uzyskać wydajność O (n) - O (1) na wartość (!) - i zużycie pamięci O (log n) traktując best()
jako tabelę odnośników, którą stopniowo rozszerzam. Obecnie oszczędza pamięć, iterując za każdym razem, ale wykonuje wiele zbędnych obliczeń. Trzymając te wartości pośrednie - i listę minimalnych wartości - mogę uniknąć zduplikowanej pracy i bardzo ją przyspieszyć. Jednak lista wartości pośrednich będzie rosła wraz z n, stąd pamięć O (log n).