siema!
tak jak w temacie poszukuję szybkiego rozwiązania dla tego problemu.
mam konto na pewnej platformie internetowej gdzie zlecane są właśnie takie zadania... myslę nad tym od kilku dni i nie mogę wydumać.. :(
oto co udało mi się napisać:
def solution(A,B,K):
if A==B:
if A%K==0:
return 1
return 0
else:
a = int((A-1)/K)
b = int(B/K)
return b-a
wyrzuca że błędy (niewłaśniwe wyniki) znajdują się końcowych elemętach przedziału
Python ma trochę wbudowanych rzeczy, które należy stosować:
def sum_numbers(start, end, n):
tmp = list(range(start, end + 1))
return sum(filter(lambda x: x % n == 0, tmp))
print(sum_numbers(1, 10, 2)) # -> 30
print(sum_numbers(10, 15, 2)) # -> 36
EDIT: Niepotrzebna jest list Przy tworzeniu tmp, filter wezmie iterator range, tak bedzie wydajniej.
kurde... dzięki!
bardziej chodziło mi o coś takiego:
def solution(A,B,K)
tmp = list(range(A,B + 1))
a = len(list(filter(lambda x: x % K == 0, tmp)))
return a
ale dzięki bo naprowadziłeś mnie na te funkcje :)
Nie musisz tworzyć tej zmiennej a wystarczy:
def solution(A,B,K):
tmp = list(range(A,B + 1))
return len(list(filter(lambda x: x % K == 0, tmp)))
Ha, ha, ha zliczanie, a mi ze zliczania zrobiło się sumowanie:), ale praktycznie rozwiązane:)
Jeszcze jedno, prawdziwi Pythoniści:) polecają (ukradzione z Haskella:)) list comprehension, więc zrobiliby to tak:
def length_nums(start, end, n):
return len([x for x in range(start, end + 1) if x % n == 0])
chyba się nie zrozumieliśmy
nie chodzi o to aby kod 1 albo 0.5 linijki tylko o to aby szybko się wykonywał...
Nie no, patrząc teoretycznie na złożoność, to oba rozwiązania są takie same O(n) razy złożoność mnożenia(x % 2), ale poszedłbym o piwo, że list comprehension będzie troszkę szybsze:)
no i wygrałbyś to piwo... :)
zobacz na swoje oryginalne rozwiazanie ktore wyglada dobrze, ale niekompletnie co zwroci gdy A=0. zobacz tez czy liczby moga byc ujemne i czy moga byc wieksze nic zakres int
zasugerowałeś podobne rozwiązanie do tego które było w pierwszym poscie tylko że złe
(zrzut ekranu)
@lion137 ma rację, python-fan-boy'e preferują jednolinijkowce, zwłaszcza gdy jest to rozwiązywane prostym (nie rekurencyjnym i nie podwójnie zagnieżdżonym) generatorem.
Jednak jest pewno ale. To można rozwiązać równaniem, które działa szybciej od generatorów, ponieważ zadanie jest algorytmiczne co widać po wysokich liczbach na screenie :).
Da się wyliczyć ile liczb w danym przedziale jest podzielnych przez daną liczbę :).
Pomocne tu będzie dzielenie całkowite, odejmowanie by znaleźć tylko pierwszey element podzielny. A w wypadku gdy nie znajdzie, należy zwrócić zero.
Powodzenia z najcięższymi testami :D. Jak nie wpadniesz na rozwiązanie, to mogę zasugerować jakiś sposób ;)
@Guaz: Rzeczywiscie, to sie wylicza:), na szybko rzucilem odruchowo co jest bibliotece jezyka, zwykle to dobry ruch
W ogóle źle do tego podchodzisz, bo problem jest czysto matematyczny a nie algorytmiczny. Wychodzimy od tego że liczby podzielne przez k są postaci k*i gdzie i to kolejne liczby całkowite. Chcemy więc znaleźć najmniejszą liczbę postaci k*i w przedziale [A,B] oraz największą liczbę tej postaci a wynikiem będzie max_i - min_i - 1max_i - (min_i - 1). Znalezienie tych liczb jest generalnie dość proste, bo wystarczy wykonać dzielenie.
Załóżmy sobie k=17 i przedział [100,1000]
ceil(100/17) = 6 więc najmniejsza liczba postaci k*i w podanym przedziale to 6*17 = 102
floor(1000/17) = 58 więc największa liczba postaci k*i w podanym przedziale to 58*17 = 986
Wynika z tego że liczb tejże postaci jest 58 - (6 - 1) = 53, co możesz sprawdzić tą swoją naiwną pętlą.
W efekcie rozwiązanie uzyskujemy w czasie stałym ze względu na operacje elementarne na liczbach (robimy dwa dzielenia i dwa odejmowania). Realistycznie to jest oczywiście złożoność log(n) względem liczby bitów w liczbach na których operujemy.
Załóżmy sobie, że k = 17 i przedział jest [17,17]. Dostaniemy, że liczb podzielnych przez 17 jest -1. Powinno być max_i - (min_i - 1).
wreszczie ktoś zrozumiał i pomógł :)