Bir listenin EKOK'u
Görev tanımı
Problem
Birkaç otobüs sıfır zamanında aynı garajdan çıkıyor ve i. otobüs her nums[i] dakikada bir dönüyor. Hepsinin garajda birlikte olduğu ilk pozitif dakikayı döndür; bu, değerlerin en küçük ortak katıdır (EKOK). Her değer pozitif bir tam sayı ve listede en az bir değer var.
Örnekler
Input: nums = [4, 6, 10]
Output: 60
Neden: 60, 4'e, 6'ya ve 10'a bölünen en küçük sayı
Input: nums = [12, 18, 24]
Output: 72
Neden: değerler çarpan paylaşıyor, bu yüzden cevap çarpımlarının çok altında
Input: nums = [9]
Output: 9
Neden: edge case: tek bir otobüs kendisiyle ilk dönüşünde buluşur
İpuçları
0 / 3
Önce iki değer için çöz. Çarpımları her zaman bir ortak kattır ama her ortak çarpanı iki kez sayar.
İki değer a ve b için en küçük ortak kat, a çarpı b'nin en büyük ortak bölenlerine bölümüdür; Öklid algoritması da o böleni hızla bulur.
Listeyi katla: 1'den başlayan kümülatif bir cevap tut ve onu iki değer formülüyle sırayla her değerle birleştir. Ara sayılar küçük kalsın diye çarpmadan önce böl.
- Hedef zaman
- O(n log(max(nums)))
- Hedef alan
- O(1)
Kısıtlar
- every value is a positive integer
- the list holds at least one value
Çözüm
İki sayının en küçük ortak katı, çarpımlarının en büyük ortak bölenlerine (EBOB) bölümüdür, çünkü bölen tam olarak iki sayının da katkı yaptığı kısımdır ve çarpım onu iki kez sayar. İşlem birleşmeli olduğu için bütün listenin cevabı değerleri birer birer kümülatif bir sonuca katlayarak kurulur. Kümülatif sonucu çarpmadan önce bölene bölmek her ara değeri son cevaptan büyük olmayacak şekilde tutar. Her adım bir Öklid çağrısına mal olur; en büyük değer M için zaman O(n log M), alan O(1).
from math import gcd
def lcm_all(nums):
result = 1
for x in nums:
result = result // gcd(result, x) * x # divide first: stays small
return result
print(lcm_all([4, 6, 10])) # -> 60
print(lcm_all([12, 18, 24])) # -> 72
print(lcm_all([9])) # -> 9
print(lcm_all([2, 3, 5, 7, 11, 13])) # -> 30030Kodda değil de fikirde mi takıldın? EBOB ve Öklid bunu anlatıyor.