Happy Number

Q: Neden süreç her zaman 1'e ya da bir döngüye ulaşır?

d basamaklı bir sayı en fazla 81 × d değerine eşlenir; bu nedenle büyük sayılar hızla küçülür: 2^31-1 değerine kadar olan herhangi bir başlangıç sayısı bir adım sonra 1000'in altına düşer ve 1000'in altındaki bir sayı en fazla 243'e eşlenir. Bu yürüyüş 1000'den az değer arasında sıkışıp kalır; dolayısıyla değerlerden birini yeniden ziyaret etmek zorundadır ve o andan itibaren döngüye girer. Kendisine eşlenen tek sayı 1'dir.

Q: Happy Number'ın zaman karmaşıklığı nedir?

İlk adım, n sayısının O(log n) basamağını okur. Sonraki her değer 1000'in altındadır ve yürüyüş en fazla 20 sayı içinde tekrar eder; bu nedenle toplam süre O(log n) olur. Hash kümesi sürümü ziyaret edilen sayıları saklar; Floyd sürümü O(1) alan kullanır.

KolayHızlı ve yavaş işaretçiler Hashing

+10

Pozitif bir tam sayı olan n ile başlayın ve onu tekrar tekrar rakamlarının kareleri toplamıyla değiştirin. Örneğin, 12 sayısı 1² + 2² = 5 olur. Bu işlem 1'e ulaşırsa n mutlu sayıdır; aksi hâlde 1'i hiç içermeyen sayılar arasında sonsuza dek döngüye girer. n mutlu sayıysa true, değilse false döndürün.

Fonksiyon

isHappy(n: integer) → boolean

ninteger: test edilecek pozitif tam sayı
Döndürürboolean: Rakamların kareleri toplamını tekrarlamak 1'e ulaşıyorsa true, sonsuza kadar döngüye giriyorsa false

Kısıtlar

1 ≤ n ≤ 2³¹-1

Örnekler

Girdi: n = 7
Çıktı: true
Açıklama: 7, 49 olur; sonra 4² + 9² = 97, ardından 130, sonra 10 ve son olarak 1. Süreç 1'e ulaştığından 7 mutludur.

Girdi: n = 2
Çıktı: false
Açıklama: 2, 4'e, 16'ya, 37'ye, 58'e, 89'a, 145'e, 42'ye, 20'ye dönüşür ve sonra tekrar 4'e ulaşır. Bundan sonra aynı sekiz sayı sonsuza kadar tekrarlanır ve hiçbir zaman 1'e ulaşmaz.

Girdi: n = 100
Çıktı: true
Açıklama: 1² + 0² + 0² = 1 olduğundan, 100 bir adım sonra 1 değerine ulaşır.

Gönderirken +16 gizli test

Ek soru

1'den 10^6'ya kadar olan mutlu sayıları, her başlangıçtan itibaren sıfırdan ilerlemek yerine 1000'in altındaki sayıların yanıtlarını yeniden kullanarak hızlıca nasıl sayarsınız?

İpuçları

Tek tek açın. Her biri biraz daha fazlasını gösterir.

3 ipucundan 0 açıldı

Çözüm

Yürüyüş sonsuza kadar devam edemez. 10 basamaklı bir sayı en fazla 10 × 81 = 810 değerine, 1000'in altındaki bir sayı ise en fazla 3 × 81 = 243 değerine eşlenir; dolayısıyla bir adımdan sonra yürüyüş 1000'den az değer arasında kalır ve 1'e ulaşmak ya da bir sayıyı tekrarlamak zorundadır. Böylece problem döngü tespitine dönüşür: gördüklerini hatırla ya da yavaş ve hızlı bir yürüyüşçü çalıştırıp karşılaşıp karşılaşmadıklarına bak.

Gördüğün tüm sayıları hatırla

Sezgi

Diziyi dolaşın ve her sayıyı bir karma kümesinde tutun. Bir sayıdan sonraki sayıya geçmeden önce, sayının kümede olup olmadığını kontrol edin. 2 için küme 2, 4, 16, 37, 58, 89, 145, 42 ve 20 ile dolar ve sonraki değer 4 olur; bu değer zaten kümededir: dolaşım, 1'e ulaşmadan bir döngüyü tamamlamıştır, dolayısıyla 2 mutlu sayı değildir. 1'e ulaşmak dolaşımı true ile bitirir.

Bu doğrudur, çünkü sonraki sayı yalnızca mevcut sayıya bağlıdır. Bir sayı tekrar ortaya çıktığında, ondan sonraki her şey aynen tekrar eder; dolayısıyla yeni bir sayı ortaya çıkamaz ve 1'e hiçbir zaman ulaşılmaz.

Dolaşım kısadır. İlk adım, n sayısının O(log n) basamağını okur ve sonraki her değer 1000'in altındadır; bu aralıkta hiçbir dolaşım, 1'e ulaşmadan veya bir sayı tekrarlanmadan önce 20'den fazla farklı sayıyı ziyaret etmez. Küme bu sayıları tutar. C kodu, küme olarak 1000 elemanlı bir bayrak dizisi kullanır ve her değerin 1000'in altında olduğu ilk adımdan sonra kayıt tutmaya başlar.

Algoritma

Boş bir hash kümesi seen oluştur.
n 1 değilken, n seen içindeyse false döndür.
Aksi takdirde n'i seen'e ekle ve n'i basamaklarının kareleri toplamıyla değiştir.
Döngü sona erdiğinde n 1'dir: true döndür.

def digitSquareSum(n):
    total = 0
    while n > 0:
        digit = n % 10
        total += digit * digit
        n //= 10
    return total


def isHappy(n):
    seen = set()
    while n != 1:
        if n in seen:
            return False  # back at an earlier number: a loop without 1
        seen.add(n)
        n = digitSquareSum(n)
    return True

Hızlı ve yavaş yürüyenler (Floyd’un döngü tespiti)

Sezgi

Her sayıyı, basamaklarının kareleri toplamını gösteren tek bir oka sahip bir düğüm olarak düşünün. n'den başlayarak okları izlemek ya oku tekrar 1'i gösteren 1'e ulaşır ya da bir döngüye girer. Bu, döngü içerebilen bağlı bir listenin yapısıdır ve Floyd algoritması hiçbir şey depolamadan döngüyü algılar: slow her turda bir adım, fast ise iki adım ilerler.

Döngü 1'i içermiyorsa iki izleyici de döngünün içinde dönmeye başlar ve her turda fast, slow'a göre bir adım kazanır; böylece aralarındaki fark, aynı sayıda buluşana kadar birer birer azalır. 2 için yedi tur sonra 42'de buluşurlar. İzleme 1'e ulaşırsa fast önce oraya varır ve orada kalır; çünkü 1'in basamaklarının kareleri toplamı 1'dir. Bu nedenle fast 1 olduğunda veya izleyiciler buluştuğunda durun ve fast'in 1 olup olmadığını yanıtlayın.

7 için slow 7, 49, 97 şeklinde ilerlerken fast 49, 130, 1 şeklinde ilerler ve döngü fast 1'deyken durur. Tur sayısı, izleme uzunluğunun en fazla küçük bir katıdır; bu nedenle çalışma süresi küme sürümüyle aynıdır ve bellek kullanımı iki tamsayıdır.

Algoritma

Bir sayının rakamlarının kareleri toplamını döndüren bir yardımcı işlev yazın.
slow = n değerini ayarlayın ve fast değerini n sayısından bir adım sonraki sayıya ayarlayın.
fast 1 olmadığı ve slow, fast'ten farklı olduğu sürece slow değerini bir adım, fast değerini iki adım ilerletin.
fast değerinin 1 olup olmadığını döndürün.

def digitSquareSum(n):
    total = 0
    while n > 0:
        digit = n % 10
        total += digit * digit
        n //= 10
    return total


def isHappy(n):
    slow = n
    fast = digitSquareSum(n)
    # fast moves two steps for every step of slow; they meet only inside a loop.
    while fast != 1 and slow != fast:
        slow = digitSquareSum(slow)
        fast = digitSquareSum(digitSquareSum(fast))
    return fast == 1

Tuzaklar ve uç durumlar

Rakam işlemleri kısadır. Hataların çoğu döngünün ne zaman durduğuyla ilgilidir.

Başka bir çıkış koşulu olmadan değer 1 olana kadar döngüye devam etmek. 2 için bu döngü hiç bitmez.
slow ve fast değişkenlerini aynı sayıdan başlatıp ilk adımdan önce slow != fast koşulunu sınamak. Döngü hiç çalışmaz ve 7 mutsuz çıkar. fast değişkenini bir adım önde başlat ya da ilk karşılaştırmadan önce ikisini de ilerlet.
Floyd sürümünde slow == 1 döndürmek. fast önce 1'e ulaşır ve döngü hemen durur; bu sırada slow hâlâ 97'de olabilir.
Rakamların kareleri yerine rakamları toplamak ya da sayının tamamının karesini almak. 12 için sonraki değer 1² + 2² = 5 olur; 3 ya da 144 değil.
Gezginler buluştuğunda n sayısını mutsuz ilan etmek. 1 kendisine eşlendiğinden gezginler 1'de de buluşur; buluştukları sayıyı kontrol et ya da fast 1 olur olmaz dur.

Sıkça sorulan sorular4

Neden süreç her zaman 1'e ya da bir döngüye ulaşır?

d basamaklı bir sayı en fazla 81 × d değerine eşlenir; bu nedenle büyük sayılar hızla küçülür: 2^31-1 değerine kadar olan herhangi bir başlangıç sayısı bir adım sonra 1000'in altına düşer ve 1000'in altındaki bir sayı en fazla 243'e eşlenir. Bu yürüyüş 1000'den az değer arasında sıkışıp kalır; dolayısıyla değerlerden birini yeniden ziyaret etmek zorundadır ve o andan itibaren döngüye girer. Kendisine eşlenen tek sayı 1'dir.

Happy Number'ın zaman karmaşıklığı nedir?

İlk adım, n sayısının O(log n) basamağını okur. Sonraki her değer 1000'in altındadır ve yürüyüş en fazla 20 sayı içinde tekrar eder; bu nedenle toplam süre O(log n) olur. Hash kümesi sürümü ziyaret edilen sayıları saklar; Floyd sürümü O(1) alan kullanır.

Neden tüm mutsuz sayılar 4'te sonlanır?

1000'in altındaki her sayıyı kontrol ettiğimizde, 1'den kaçınan tam olarak bir döngü olduğunu görürüz: 4, 16, 37, 58, 89, 145, 42, 20 ve tekrar 4. Her başlangıç değeri 1000'in altına düştüğünden, mutlu olmayan her sayı bu döngüye girer. Bir çözüm 4'e ulaşır ulaşmaz durabilir, ancak bu, bir mülakatta gerekçelendirmeniz gereken bir gerçeğe dayanır; küme ve Floyd'un yöntemi böyle bir bilgi gerektirmez.

Mutlu Sayı, Bağlı Liste Döngüsü ile nasıl ilişkilidir?

Her ikisi de, her öğeden bir ok izlendiğinde daha önce ziyaret edilmiş bir öğeye geri dönülüp dönülmediğini sorar. Mutlu Sayı probleminde ok, rakamların kareleri toplamıdır; bağlı listede ise sonraki işaretçidir. Bu nedenle Floyd'un hızlı ve yavaş ilerleyen işaretçileri her iki problemi de sabit bellek kullanarak çözer.

Python

def isHappy(n):
    # Kodu buraya yazın

Test durumları

Durum 1

Durum 2

Durum 3

Girdi

n = 7

Beklenen

true