Happy Number

Q: لماذا تصل العملية دائمًا إلى 1 أو إلى حلقة؟

العدد الذي يحتوي على d من الأرقام يُحوَّل إلى قيمة لا تتجاوز 81 × d ، لذا تتقلص الأعداد الكبيرة بسرعة: كل عدد ابتدائي لا يتجاوز 2^31-1 يصبح أقل من 1000 بعد خطوة واحدة، والعدد الأقل من 1000 يُحوَّل إلى قيمة لا تتجاوز 243. يظل المسار محصورًا بين أقل من 1000 قيمة، لذا لا بد أن يعيد زيارة إحدى القيم، ومنذ ذلك الحين يدخل في دورة. العدد 1 هو العدد الوحيد الذي يُحوَّل إلى نفسه.

Q: ما هو التعقيد الزمني لرقم سعيد؟

تقرأ الخطوة الأولى الأرقام O(log n) للعدد n . كل قيمة لاحقة أقل من 1000، وتتكرر المسيرة خلال 20 عددًا على الأكثر، لذا يكون الزمن الإجمالي O(log n) . يخزّن إصدار مجموعة التجزئة الأعداد التي تمت زيارتها؛ ويستخدم إصدار فلويد مساحة O(1) .

سهلالمؤشران السريع والبطيء التجزئة

+10

ابدأ بعدد صحيح موجب n واستبدله بمجموع مربعات أرقامه، وكرر ذلك مرارًا. على سبيل المثال، يصبح 12 هو 1² + 2² = 5. إذا وصلت هذه العملية إلى 1، فإن n عدد سعيد؛ وإلا فإنه يظل يدور إلى الأبد عبر أعداد لا تتضمن 1 مطلقًا. أعد true إذا كان n عددًا سعيدًا، وfalse إذا لم يكن كذلك.

الدالة

isHappy(n: integer) → boolean

ninteger: العدد الصحيح الموجب المراد اختباره
تُرجعboolean: صحيح إذا أدى تكرار مجموع مربعات الأرقام إلى الوصول إلى 1، وخطأ إذا استمر في الدوران إلى الأبد

القيود

1 ≤ n ≤ 2³¹-1

أمثلة

المدخلات: n = 7
المخرجات: true
الشرح: يصبح 7 هو 49، ثم 4² + 9² = 97، ثم 130، ثم 10، ثم 1. تصل العملية إلى 1، لذا فإن 7 عدد سعيد.

المدخلات: n = 2
المخرجات: false
الشرح: يصبح 2 هو 4، ثم 16، و37، و58، و89، و145، و42، و20، ثم 4 مرة أخرى. ومن هناك تتكرر الأعداد الثمانية نفسها إلى الأبد ولا تصل أبدًا إلى 1.

المدخلات: n = 100
المخرجات: true
الشرح: 1² + 0² + 0² = 1، لذا يصل 100 إلى 1 بعد خطوة واحدة.

+16 اختبارات مخفية عند الإرسال

سؤال إضافي

كيف يمكنك عدّ الأعداد السعيدة من 1 إلى 10^6 بسرعة، مع إعادة استخدام الإجابات للأعداد الأقل من 1000 بدلاً من البدء من الصفر لكل عدد؟

تلميحات

افتحها واحدًا تلو الآخر. كل تلميح يكشف أكثر قليلًا.

فُتح 0 من 3

الحل

لا يمكن للمسار أن يستمر إلى ما لا نهاية. فالعدد المؤلف من 10 أرقام يقابل قيمة لا تتجاوز 10 × 81 = 810، والعدد الأصغر من 1000 يقابل قيمة لا تتجاوز 3 × 81 = 243، لذا بعد خطوة واحدة يبقى المسار ضمن أقل من 1000 قيمة، ولا بد أن يصل إلى 1 أو يكرر عددًا. وهذا يحوّل المسألة إلى اكتشاف دورة: تذكّر ما رأيته، أو استخدم متتبعًا بطيئًا وآخر سريعًا وتحقق مما إذا كانا سيلتقيان.

تذكّر كل رقم رأيته

الفكرة

تتبّع التسلسل واحتفظ بكل عدد في مجموعة تجزئة. قبل الانتقال من عدد، تحقّق مما إذا كان موجودًا بالفعل في المجموعة. بالنسبة إلى 2، تمتلئ المجموعة بالأعداد 2 و4 و16 و37 و58 و89 و145 و42 و20، والقيمة التالية هي 4، وهي موجودة بالفعل: لقد أُغلق المسار على حلقة من دون الوصول إلى 1، لذا فإن 2 ليس عددًا سعيدًا. الوصول إلى 1 ينهي المسار بالقيمة true.

هذا صحيح لأن العدد التالي يعتمد فقط على العدد الحالي. ما إن يعود عدد للظهور، حتى يتكرر كل ما يأتي بعده بالضبط، لذا لا يمكن أن يظهر أي عدد جديد، ولن يظهر 1 أبدًا.

المسار قصير. تقرأ الخطوة الأولى أرقام n ذات التعقيد O(log n)، وكل قيمة لاحقة أقل من 1000، حيث لا يزور أي مسار أكثر من 20 عددًا مختلفًا قبل أن يصل إلى 1 أو يكرر عددًا. تحتوي المجموعة على تلك الأعداد. يستخدم كود C مصفوفة أعلام من 1000 خانة كمجموعة، ويبدأ التسجيل بعد الخطوة الأولى، حين تكون كل قيمة أقل من 1000.

الخوارزمية

أنشئ مجموعة تجزئة فارغة seen.
ما دام n لا يساوي 1، فأعِد false إذا كان n موجودًا في seen.
وإلا، أضف n إلى seen واستبدل n بمجموع مربعات أرقامه.
عند انتهاء الحلقة، تكون قيمة n هي 1: أعِد true.

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

المؤشران السريع والبطيء (اكتشاف الدورة لخوارزمية فلويد)

الفكرة

تخيّل كل عدد على أنه عقدة لها سهم واحد يشير إلى مجموع مربعات أرقامه. باتباع الأسهم انطلاقًا من n، إما أن تصل إلى 1، الذي يشير سهمه إلى 1، أو تدخل في حلقة. هذا هو شكل قائمة مترابطة قد تحتوي على دورة، وخوارزمية Floyd تكشف الدورة دون تخزين أي شيء: يتحرك slow خطوة واحدة في كل جولة، بينما يتحرك fast خطوتين.

إذا لم تتضمن الحلقة العدد 1، فسينتهي كلا المتحركين بالدوران فيها، وفي كل جولة يكتسب fast خطوة واحدة على slow، لذا تتقلص الفجوة بمقدار واحد حتى يقفا عند العدد نفسه. بالنسبة إلى 2، يلتقيان عند 42 بعد سبع جولات. إذا وصل المسار إلى 1، فسيصل إليه fast أولًا ويبقى هناك، لأن مجموع مربعات أرقام 1 هو 1. لذا توقّف عندما يكون fast هو 1 أو عندما يلتقي المتحركان، ثم تحقّق مما إذا كان fast هو 1.

بالنسبة إلى 7، يتحرك slow عبر 7 و49 و97، بينما يتحرك fast عبر 49 و130 و1، وتتوقف الحلقة مع وجود fast عند 1. عدد الجولات لا يتجاوز مضاعفًا صغيرًا لطول المسار، لذا فإن الزمن يماثل نسخة المجموعة، والذاكرة اللازمة هي عددان صحيحان.

الخوارزمية

اكتب دالة مساعدة تُعيد مجموع مربعات أرقام عدد.
عيّن slow = n، وعيّن fast إلى العدد الذي يأتي بعد n بخطوة واحدة.
ما دام fast لا يساوي 1 وslow لا يساوي fast، حرّك slow خطوة واحدة وfast خطوتين.
أعِد ما إذا كان fast يساوي 1.

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

أخطاء شائعة وحالات حدّية

حساب الأرقام موجز. معظم الأخطاء تتعلق بموعد توقف الحلقة.

التكرار حتى تصبح القيمة 1 من دون أي شرط خروج آخر. بالنسبة إلى 2، لن تنتهي هذه الحلقة أبدًا.
بدء slow وfast عند العدد نفسه والتحقق من slow != fast قبل الخطوة الأولى. لن تُنفَّذ الحلقة، وستُصنَّف 7 على أنها غير سعيدة. ابدأ fast متقدمًا بخطوة، أو حرّك كليهما قبل المقارنة الأولى.
إرجاع slow == 1 في نسخة فلويد. يصل fast إلى 1 أولًا وتتوقف الحلقة فورًا، بينما قد يظل slow عند 97.
جمع الأرقام بدلًا من مربعاتها، أو تربيع العدد كله. بالنسبة إلى 12، القيمة التالية هي 1² + 2² = 5، وليست 3 ولا 144.
اعتبار n غير سعيد كلما التقى المؤشّران. فالعدد 1 يحيل إلى نفسه، لذا يلتقي المؤشّران عند 1 أيضًا؛ تحقّق من مكان التقائهما، أو توقّف فورًا عندما يصبح fast هو 1.

أسئلة شائعة4

لماذا تصل العملية دائمًا إلى 1 أو إلى حلقة؟

العدد الذي يحتوي على d من الأرقام يُحوَّل إلى قيمة لا تتجاوز 81 × d، لذا تتقلص الأعداد الكبيرة بسرعة: كل عدد ابتدائي لا يتجاوز 2^31-1 يصبح أقل من 1000 بعد خطوة واحدة، والعدد الأقل من 1000 يُحوَّل إلى قيمة لا تتجاوز 243. يظل المسار محصورًا بين أقل من 1000 قيمة، لذا لا بد أن يعيد زيارة إحدى القيم، ومنذ ذلك الحين يدخل في دورة. العدد 1 هو العدد الوحيد الذي يُحوَّل إلى نفسه.

ما هو التعقيد الزمني لرقم سعيد؟

تقرأ الخطوة الأولى الأرقام O(log n) للعدد n. كل قيمة لاحقة أقل من 1000، وتتكرر المسيرة خلال 20 عددًا على الأكثر، لذا يكون الزمن الإجمالي O(log n). يخزّن إصدار مجموعة التجزئة الأعداد التي تمت زيارتها؛ ويستخدم إصدار فلويد مساحة O(1).

لماذا تنتهي جميع الأعداد غير السعيدة عند 4؟

يُظهر التحقق من كل عدد أقل من 1000 وجود حلقة واحدة فقط لا تصل إلى 1: 4، 16، 37، 58، 89، 145، 42، 20، ثم تعود إلى 4. وبما أن كل نقطة بداية تنخفض إلى أقل من 1000، فإن كل عدد غير سعيد يقع فيها. يمكن للحل أن يتوقف بمجرد أن يصل إلى 4، لكن ذلك يعتمد على حقيقة سيتعين عليك تبريرها في مقابلة؛ أما المجموعة وطريقة فلويد فلا تتطلبان معرفة كهذه.

ما العلاقة بين الرقم السعيد ودورة القائمة المرتبطة؟

كلاهما يسأل عمّا إذا كان اتباع سهم واحد من كل عنصر يعيدك في أي وقت إلى عنصر سبق أن زرته. في مسألة العدد السعيد، يكون السهم هو مجموع مربعات الأرقام؛ وفي القائمة المرتبطة، يكون هو المؤشر إلى العنصر التالي. لهذا السبب يحلّ متتبعا فلويد، السريع والبطيء، المسألتين باستخدام ذاكرة ثابتة.

Python

def isHappy(n):
    # اكتب الكود هنا

حالات الاختبار

الحالة 1

الحالة 2

الحالة 3

المدخلات

n = 7

المتوقع

true