PWC 397: Eksik En Küçük Pozitif Sayıyı Bulma

Perl Weekly Challenge 397'nin ilk görevi, bir dizide ortalamadan büyük olan en küçük eksik pozitif tamsayıyı bulmak. Basit görünse de, eksik olan değeri verimli bir şekilde tespit etmek biraz dikkat gerektiriyor.

Önce diziyi oku, tüm elemanların toplamını hesapla ve ortalamayı bul. Sonra ortalamadan büyük olan pozitif tamsayıları sırayla kontrol et. Hangi sayı dizide yoksa, o senin cevabın.

Python ile yazacak olsan:

1def absent_smallest_positive(arr):
2average = sum(arr) / len(arr)
3candidate = int(average) + 1
4arr_set = set(arr)
5
6while candidate in arr_set:
7candidate += 1
8
9return candidate
10
11arr1 = [1, 2, 4, 5, 6]
12print(absent_smallest_positive(arr1)) # Çıktı: 7
13
14arr2 = [-5, -2, -1, 3]
15print(absent_smallest_positive(arr2)) # Çıktı: 1

Kod mantığı şöyle: Ortalamayı hesapladıktan sonra, ondan hemen büyük bir tamsayıdan başla. Seti kullanarak O(1) zaman içinde dizide var mı yok mu kontrol et. Bulunan ilk eksik sayı cevaptır.

Birinci örnekte ortalama 3.6, bu yüzden 4'ten başlarsın. 4, 5, 6 dizide var, ama 7 yok, işte bulduğun sayı.

İkinci örnekte ortalama -1.25, bu yüzden 0'dan başlarsın. 0 ve 1 dizide yok, ama 1 pozitif olduğu için onu döndürürsün.

Trick, negatif sayılarla başa çıkmak. Ortalama negatifse, en küçük pozitif tamsayı olan 1'den başlamak daha akıllıca olabilir. Ama yukarıdaki çözüm her durumda çalışır.

Bu tür sorular, set yapısını ve basit iterasyonu birleştirmenin gücünü gösteriyor. Performans açısından da O(n) zaman, O(n) bellek, yani optimal. Orijinal challenge'ı burada bulabilirsin.