En Büyük Grubu Sayma (1399)
Merhaba, ben Fatih Soysal ve bugün LeetCode’daki 1399. problem olan “En Büyük Grubu Sayma” problemini detaylı olarak inceleyeceğiz. Bu problem, sayıların digit toplamlarına göre gruplandırılmasını ve en büyük grubun boyutunu bulmayı gerektiriyor. Öncelikle problemi daha iyi anlamak için örneklerle başlayalım. Daha sonra, farklı çözüm yaklaşımlarını ele alacağız ve en verimli yöntemi belirleyeceğiz. Son olarak da, kod örneğini ve performans analizini paylaşacağım.
Problem Tanımı
Problem, bize 1 ile n arasında (n dahil) olan sayıları vermektedir. Her sayının basamaklarının toplamını hesaplayıp, bu toplama göre sayıları gruplıyoruz. Örneğin, 19 sayısının basamakları toplamı 1+9=10’dur. Amacımız, en büyük grubu oluşturan sayıların sayısını bulmaktır. Basit bir örnek olarak, n=10 ise; 1, 2, 3…9 sayılarının basamak toplamları kendilerine eşittir ve 10 sayısının basamak toplamı 1’dir. Burada en büyük grup 1’den 9’a kadar olan sayıları içerir, dolayısıyla cevabımız 9 olur.
Çözüm Yaklaşımları
Bu problemi çözmek için birkaç yaklaşım kullanabiliriz. En basit yaklaşım, 1’den n’ye kadar tüm sayıları tek tek işleyerek basamak toplamlarını hesaplamak ve gruplandırmak olabilir. Ancak, bu yaklaşım büyük n değerleri için oldukça yavaş olacaktır. Bu yüzden daha optimize bir yönteme ihtiyacımız var. Daha verimli bir çözüm için, bir hash table (örneğin, Python’da dictionary) kullanarak sayıların basamak toplamlarını anahtar, ve o basamak toplamına sahip sayıların sayısını değer olarak tutabiliriz. Bu sayede, her sayıyı sadece bir kez işleriz.
Kod Örneği (Python)
def countLargestGroup(n):
counts = {}
max_count = 0
for i in range(1, n + 1):
digit_sum = sum(map(int, str(i)))
counts[digit_sum] = counts.get(digit_sum, 0) + 1
max_count = max(max_count, counts[digit_sum])
return sum(1 for count in counts.values() if count == max_count)
Bu kod, öncelikle bir boş sözlük oluşturur. Sonrasında, 1’den n’ye kadar her sayı için basamakları toplamını hesaplar. Hesaplanan toplam, sözlükte anahtar olarak kullanılır ve o anahtara karşılık gelen değer (sayı adedi) 1 arttırılır. Son olarak, en büyük sayı adedini bulur ve bu adede sahip grup sayısını döndürür.
Performans Analizi
Yukarıdaki Python kodunun karmaşıklığı O(n * log(n))’dir. Çünkü her sayı için basamakları toplamını hesaplamak O(log(n)) zaman alır. Ancak, büyük n değerlerinde bile bu kod oldukça hızlı çalışır. Daha da optimize edilmesi için, basamak toplamlarının önceden hesaplanması ve saklanması gibi teknikler kullanılabilir. Bu yaklaşım, kodun yeniden kullanılabilirliğini artırarak performansı iyileştirebilir.
Sonuç
Bu makalede, LeetCode’daki 1399. problem olan “En Büyük Grubu Sayma” problemini inceledik. Farklı çözüm yaklaşımlarını değerlendirdik ve Python ile verimli bir çözüm geliştirdik. Bu problem, algoritma ve veri yapıları bilginizi test etmek için güzel bir örnektir. Daha fazla algoritma problemi çözmek ve yeteneklerinizi geliştirmek için fatihsoysal.com sitesini ziyaret edebilirsiniz. Ayrıca, daha detaylı bilgi için bu kaynak faydalı olacaktır.
Umarım bu makale size yardımcı olmuştur!
#Etiketler: En Büyük Grubu Sayma, LeetCode, 1399, Algoritma, Python, Programlama, Basamak Toplamı, Hash Table, Veri Yapıları, Performans Analizi, Fatih Soysal