Sum of Digits
لديك عدد صحيح غير سالب n. أعد مجموع أرقامه العشرية. على سبيل المثال، أرقام 482 هي 4 و8 و2، لذا فالإجابة هي 14.
الدالة
- ninteger
- العدد الصحيح غير السالب الذي تجمع أرقامه
- تُرجعinteger
- مجموع الأرقام العشرية للعدد n
القيود
0 ≤ n ≤ 231-1
أمثلة
- المدخلات
- n = 9045
- المخرجات
- 18
- الشرح
- أرقام
9045هي 9 و0 و4 و5، و9 + 0 + 4 + 5 = 18. لا يضيف الصفر شيئًا، لكنه يظل رقمًا.
- المدخلات
- n = 7
- المخرجات
- 7
- الشرح
- العدد المكوّن من رقم واحد يساوي مجموع أرقامه، لذا فإن
7يعطي7.
+15 اختبارات مخفية عند الإرسال
تلميحات
افتحها واحدًا تلو الآخر. كل تلميح يكشف أكثر قليلًا.
كيف تجد الرقم الأخير من عدد باستخدام عملية حسابية واحدة؟
الرقم الأخير هو
n % 10، والقسمة الصحيحة على 10 تزيله. وكل زوج من العمليتين يمنحك رقمًا واحدًا.احتفظ بمجموعٍ جارٍ. ما دام
nأكبر من 0، أضفn % 10إليه واقسمnعلى 10، مع التقريب إلى الأسفل.
الحل
العدد لا يعطيك أرقامه واحدًا تلو الآخر؛ عليك تفكيكه. يمكنك تحويله إلى نص وقراءة محارفه، أو استخدام العمليتين الحسابيتين اللتين تزيلان الرقم الأخير: تعطيك n % 10 هذا الرقم، والقسمة الصحيحة على 10 تزيله. تستغرق كلتاهما خطوةً واحدة لكل رقم، ويرمز إلى ذلك أدناه بـ d، وd ≤ 10 هنا. لا تحتاج الطريقة الحسابية إلى ذاكرة إضافية.
اقرأ الأرقام كنص
الفكرة
عندما تكتب عددًا، تكون أرقامه ظاهرة بالفعل. حوّل n إلى نص عشري؛ يصبح 9045 أربعة محارف هي 9 و0 و4 و5، ثم مرّ على المحارف واجمع قيمة كلٍّ منها.
المحرف ليس عددًا بعد. يُخزَّن المحرف '4' على هيئة الرمز 52، لذا حلّله أو اطرح رمز '0': '4' - '0' = 4. رموز محارف الأرقام متتالية، ولهذا ينجح هذا الطرح مع الأرقام العشرة كلها.
يتكوّن النص من d محارف، محرف واحد لكل رقم، لذا تستغرق الحلقة زمنًا قدره O(d)، ويستهلك النص نفسه مساحة إضافية قدرها O(d).
الخوارزمية
- حوّل
nإلى نص عشري. - عيّن
total = 0. - أضف قيمة كل رقم إلى
total. - أعِد
total.
def sumOfDigits(n):
total = 0
for digit in str(n):
total += int(digit)
return totalاستخرج الرقم الأخير باستخدام % 10
الفكرة
يمكنك تفكيك عدد من دون أي نص. باقي القسمة على 10 هو الرقم الأخير: 9045 % 10 = 5. القسمة الصحيحة على 10 تتخلص من ذلك الرقم: 9045 / 10 = 904 عند إسقاط الجزء الكسري. كرر هذه العملية المزدوجة وستظهر الأرقام من اليمين إلى اليسار.
بالنسبة إلى 9045: أضف 5 واحتفظ بـ 904، وأضف 4 واحتفظ بـ 90، وأضف 0 واحتفظ بـ 9، وأضف 9 واحتفظ بـ 0. تتوقف الحلقة عند 0 ويكون المجموع 18. عندما تكون n = 0، لا تُنفَّذ الحلقة مطلقًا وتكون الإجابة 0، وهذا صحيح.
تزيل كل خطوة رقمًا واحدًا، لذا فهناك d خطوات، والزمن O(d)، ولا يوجد في الذاكرة سوى عددين صحيحين، والمساحة O(1). كل قيمة وسيطة أصغر من n، لذا لا يمكن أن يحدث تجاوز للسعة.
الخوارزمية
- عيّن
total = 0. - ما دام
n > 0، أضفn % 10إلىtotal. - اقسم
nعلى 10، مع إسقاط الجزء الكسري. - عندما تصبح قيمة
nتساوي 0، أعدtotal.
def sumOfDigits(n):
total = 0
while n > 0:
total += n % 10 # last digit
n //= 10 # drop the last digit
return total
أخطاء شائعة وحالات حدّية
الحلقة قصيرة، والأخطاء تتعلق بالأنواع وأصغر قيمة إدخال.
- استخدام
/عندما تعني اللغة القسمة الحقيقية. في JavaScript وTypeScript وLua وPHP وR، تكون9045 / 10هي904.5، ثم تضيف الحلقة كسورًا. قرّب إلى الأسفل باستخدامMath.floorأوmath.floor؛ في Python استخدم//، وفي Dart استخدم~/، وفي PHP استخدمintdiv، وفي R استخدم%/%. - إضافة المحارف بدلًا من الأرقام. قيمة المحرف
'7'هي 55، وليست 7. اطرح'0'أو حلّل المحرف أولًا. - التكرار ما دام
n >= 10. عندها تتوقف الحلقة ويبقى الرقم الأيسر فيnمن دون إضافته، لذا تعطي9045الناتج 9 بدلًا من 18. كرّر ما دامn > 0، وهذا يعيد أيضًا 0 عندما تكونn = 0. - طباعة الأعداد الكبيرة كنص في R. تعطي
as.character(100000)القيمة"1e+05"، وليس الأرقام الستة للعدد. استخدمformat(n, scientific = FALSE).
أسئلة شائعة4
ما هو التعقيد الزمني لجمع أرقام عدد؟
خطوة واحدة لكل رقم، لذا فإن التعقيد هو O(d)، حيث إن d هو عدد الأرقام. يحتوي العدد n على نحو log10(n) + 1 رقمًا، لذا غالبًا ما يُكتب الحد نفسه O(log n). بالنسبة إلى عدد صحيح من 32 بت، يكون ذلك 10 خطوات كحد أقصى.
كيف تحصل على أرقام عدد دون تحويله إلى سلسلة نصية؟
استخدم باقي القسمة والقسمة الصحيحة على 10. يمثّل n % 10 الرقم الأخير، والقسمة على n على 10 مع إهمال الباقي تحذف ذلك الرقم. كرّر ذلك حتى تصل n إلى 0، وستمرّ على كل رقم من اليمين إلى اليسار.
ما هو الجذر الرقمي لعدد؟
هو ما تحصل عليه بجمع الأرقام مرارًا وتكرارًا حتى يتبقى رقم واحد: يعطي 9045 العدد 18، ثم 9. بالنسبة إلى n موجب، يساوي 1 + (n-1) % 9، لأن كل عدد يترك الباقي نفسه عند قسمته على 9 الذي يتركه مجموع أرقامه.
هل نسخة السلسلة النصية أفضل أم نسخة العمليات الحسابية؟
كلاهما بتعقيد O(d) وكلاهما صحيح. إصدار السلسلة النصية أقصر في الكتابة في كثير من اللغات، لكنه ينشئ نسخة من الأرقام. يستخدم الإصدار الحسابي ذاكرة إضافية بتعقيد O(1)، ويُظهر للمُحاوِر أنك تعرف كيف يفكك % 10 و/ 10 العدد إلى أجزائه، وهو ما يفيد في مسائل الأعداد المتناظرة وعكس الأرقام.
مسائل مشابهة
مسائل تعتمد على الأفكار نفسها. حلّ اثنتين أو ثلاث منها يثبّت النمط.
Python
def sumOfDigits(n):
# اكتب الكود هناالحالة 1
الحالة 2
المدخلات
n = 9045
المتوقع
18