Tam sayı karekök
Görev tanımı
Problem
Negatif olmayan bir tam sayı verildiğinde, karesi onu aşmayan en büyük tam sayıyı döndür. Kesirli kısım yuvarlanmaz, atılır; yani tam kare olmayan bir sayı gerçek kökünün hemen altındaki değeri verir. Hazır karekök fonksiyonlarına izin yok.
Örnekler
Input: n = 8
Output: 2
Neden: 2'nin karesi 4, 3'ün karesi 9, bu yüzden cevap 2'ye kesilir
Input: n = 16
Output: 4
Neden: tam kare kesin kökünü döndürür
Input: n = 0
Output: 0
Neden: edge case: sıfır kendi köküdür
İpuçları
0 / 3
Birden başlayarak her adayı denemek işe yarar ama büyük bir girdi için çok fazla adım sürer. Cevabın etrafındaki adaylarla nasıl ilişkili olduğuna dikkat et.
Kare almak artan bir fonksiyon; bu yüzden cevabın altındaki her aday testi geçer, üstündeki her aday başarısız olur. Adaylar temiz biçimde geçen bir bloğa ve başarısız olan bir bloğa ayrılır.
Sıfırdan sayının kendisine kadar olan aralıkta ara. Ortadaki adayı karesini alarak test et: kare sığıyorsa adayı hatırla ve üst kısımda aramaya devam et, sığmıyorsa onu ve bütün üst kısmı at. En son hatırlanan aday cevaptır.
- Hedef zaman
- O(log n)
- Hedef alan
- O(1)
Kısıtlar
- n is a non-negative integer
Çözüm
Karem sığıyor mu testi monotondur: cevaba kadar her aday için geçerlidir ve ötesindeki her aday için başarısız olur; ikiye bölen bir aramanın ihtiyaç duyduğu yapı tam olarak bu. Her tur ortadaki adayın karesini alır ve aralığın yarısını atar; son cevap hayatta kalsın diye geçtiği her seferde adayı hatırlar. Kök almak yerine kareleri karşılaştırmak her şeyi tam sayılarda tutar. Zaman O(log n), alan O(1).
def integer_sqrt(n):
low, high, best = 0, n, 0
while low <= high:
mid = (low + high) // 2
if mid * mid <= n: # mid fits, but something larger might too
best, low = mid, mid + 1
else:
high = mid - 1 # mid is too big, and so is everything above
return best
print(integer_sqrt(8)) # -> 2
print(integer_sqrt(16)) # -> 4
print(integer_sqrt(0)) # -> 0Kodda değil de fikirde mi takıldın? İkili arama bunu anlatıyor.