Count Digits
اكتب دالة تستقبل عددًا صحيحًا غير سالب n وتُرجع عدد أرقامه عند كتابته بالأساس 10 من دون أصفار بادئة. يُكتب الصفر على هيئة 0 واحدة، لذا يتكوّن من رقم واحد.
الدالة
- ninteger
- العدد الصحيح غير السالب المراد قياسه
- تُرجعinteger
- عدد الأرقام العشرية في n
القيود
0 ≤ n ≤ 231-1
أمثلة
- المدخلات
- n = 4096
- المخرجات
- 4
- الشرح
- القسمة الصحيحة على 10 تحوّل
4096إلى409و40و4. يُزال بذلك ثلاثة أرقام ويبقى رقم واحد، لذا فالإجابة هي4.
- المدخلات
- n = 0
- المخرجات
- 1
- الشرح
- يُكتب
0برقم واحد. الحلقة التي تستمر في العد ما دام العدد أكبر من 0 لا تعمل هنا، وستُرجع0بدلًا من1.
- المدخلات
- n = 100
- المخرجات
- 3
- الشرح
- الأصفار أرقام أيضًا: يُكتب
100على هيئة1و0و0، لذا فالإجابة هي3.
+16 اختبارات مخفية عند الإرسال
سؤال إضافي
هل يمكنك عدّ الأرقام دون استخدام حلقة تتكرر مرة لكل رقم، وذلك مثلًا باستخدام البحث الثنائي بين قوى العدد 10؟
تلميحات
افتحها واحدًا تلو الآخر. كل تلميح يكشف أكثر قليلًا.
ماذا يحدث لعدد الأرقام عندما تقسم عددًا على 10 وتتجاهل الباقي؟
كل قسمة صحيحة على 10 تزيل رقمًا واحدًا بالضبط من النهاية. احسب عدد مرات القسمة اللازمة للوصول إلى رقم واحد.
ابدأ عدّادًا عند 1 واقسم على 10 ما دام العدد أكبر من أو يساوي 10، مع إضافة 1 في كل مرة. البدء من 1 يعطي أيضًا الإجابة الصحيحة لـ
0.
الحل
عدد الخانات هو عدد المرات التي يمكنك فيها القسمة على 10 قبل أن يتبقى رقم واحد، مضافًا إليه ذلك الرقم. الفكرة تتسع في سطر واحد؛ أما العمل فيكمن في الحالات الحدّية. يحتوي 0 على خانة واحدة، ويتغير العدد بين 9 و10، كما أن الصيغة القائمة على اللوغاريتم لا تعمل مع 0، وفي حساب الفاصلة العائمة قد تفشل عند قيمة أقل قليلًا من قوى العشرة الكبيرة.
اكتب الرقم كنص وعدّ الأحرف
الفكرة
تعرف لغتك بالفعل كيفية كتابة n بالنظام العشري. اطلب منها هذه السلسلة النصية وعدّ الأحرف: يصبح 4096 "4096"، أي أربعة أحرف. ويصبح 0 "0"، أي حرفًا واحدًا، لذا لا يحتاج الصفر إلى حالة خاصة.
يقسم التحويل على 10 داخل المكتبة، مرة واحدة لكل رقم، لذا يكون مقدار العمل O(log n). تحتوي السلسلة النصية على حرف واحد لكل رقم، وهذا يعني استخدام ذاكرة إضافية بمقدار O(log n)، وبحد أقصى 10 أحرف هنا.
يجب أن يكون التنسيق عشريًا عاديًا. في R، تعطي as.character(1e5) القيمة "1e+05"، أي خمسة أحرف لعدد مكوّن من ستة أرقام، لذا استخدم sprintf("%.0f", n) للتنسيق. في Lua 5.3 والإصدارات الأحدث، تحافظ tostring(4096.0) على .0، بينما تكتب string.format("%d", n) العدد الصحيح في جميع الإصدارات.
الخوارزمية
- حوّل
nإلى سلسلة نصية عشرية باستخدام دالة لا تتحول أبدًا إلى التدوين العلمي. - احسب عدد أحرف السلسلة.
- أعِد ذلك العدد. بالنسبة إلى
0، تكون السلسلة"0"، لذا تكون الإجابة1من دون أي فحص إضافي.
def countDigits(n):
return len(str(n))اقسم على 10 حتى يتبقى رقم واحد
الفكرة
القسمة الصحيحة على 10 تزيل الرقم الأخير: 4096 / 10 تساوي 409. تزيل كل قسمة رقمًا واحدًا، لذا فإن عدد مرات القسمة اللازمة للوصول إلى رقم واحد، زائد واحد لذلك الرقم الأخير، هو الإجابة. يحتاج 4096 إلى ثلاث عمليات قسمة (409، 40، 4)، لذا فهو يتكون من 4 أرقام.
ابدأ العد من 1، واقسم ما دام n ≥ 10. البدء من 1 يعني أن لكل عدد رقمًا واحدًا على الأقل، وهذا ينطبق تمامًا على 0. أما الطريقة التي يبدأ الناس عادةً بكتابتها، وهي العد من 0 ما دام n > 0، فتعيد 0 عندما يكون n = 0، وتحتاج إلى فحص منفصل.
تُنفَّذ الحلقة مرة واحدة لكل رقم بعد الأول، وبحد أقصى 9 مرات للقيمة 2147483647، لذا يستغرق ذلك زمنًا قدره O(log n). وتستخدم عدّادًا واحدًا وتغيّر نسختها الخاصة من n، لذا فالمساحة الإضافية هي O(1).
الخوارزمية
- عيّن
count = 1للرقم الموجود دائمًا. - ما دام
n ≥ 10، اقسمnعلى 10 باستخدام القسمة الصحيحة، وأضف 1 إلىcount. - عندما يتبقى رقم واحد، أعد
count.
def countDigits(n):
count = 1 # every number, 0 included, has at least one digit
while n >= 10:
n //= 10
count += 1
return count
أخطاء شائعة وحالات حدّية
يقع كل خطأ في هذه المسألة عند حدٍّ ما.
- العدّ بدءًا من 0 ما دام
n > 0. هذا صحيح لكل عدد موجب، ويُرجع0عندما يكونn = 0. - استخدام
floor(log10(n)) + 1. يفشل هذا مع0، إذ يكون اللوغاريتم سالب ما لا نهاية، وكذلك مع القيم الكبيرة الأقل قليلًا من إحدى قوى العدد 10: ففي الدقة المضاعفة، تُقرَّبlog10(10^15-1)إلى15تمامًا، لذا تعطي الصيغة 16 رقمًا بدلًا من 15. - استخدام القسمة الحقيقية في حلقة تستمر ما دام
n > 0. في JavaScript وLua وPHP وR، تحتفظ/بالجزء الكسري، لذا تتناقص4096مقتربةً من 0 على مدى 328 خطوة قبل أن تصل إليه. استخدمMath.floorأوmath.floorأوintdivأو%/%. - الترميز بالصيغة العلمية في النسخة التي تستخدم سلسلة نصية: تكتب R القيمة
100000على شكل"1e+05". - احتساب إشارة السالب على أنها رقم. الإدخال هنا ليس سالبًا أبدًا، لكن
String(-42)يتكون من ثلاثة أحرف، لذا فإن النسخة المخصصة للأعداد السالبة تأخذ القيمة المطلقة أولًا.
أسئلة شائعة4
كيف تعدّ أرقام عدد دون تحويله إلى سلسلة نصية؟
اقسمه على 10 باستخدام القسمة الصحيحة حتى يتبقى رقم واحد، مع عدّ مرات القسمة، وأضف 1 للرقم الأخير. تصبح 4096 409، ثم 40، ثم 4: ثلاث عمليات قسمة، أي 4 أرقام. تستخدم الحلقة مساحة إضافية O(1).
لماذا يتكوّن العدد 0 من رقم واحد؟
يُكتب الصفر بالحرف 0 وحده، لذا يتكوّن تمثيله العشري من رقم واحد. لا يُنفَّذ الكود الذي يحسب عدد مرات القسمة ما دام العدد أكبر من 0 عندما يكون العدد 0، ويُرجع 0. يبدأ العداد من 1، وتُجرى القسمة ما دام العدد أكبر من أو يساوي 10، وبذلك يُعالَج الصفر دون حالة خاصة.
هل يمكنك استخدام log10 لعدّ أرقام عدد؟
لـ n موجب، يكون العدد floor(log10(n)) + 1، لكن يُحسب اللوغاريتم باستخدام الأعداد ذات الفاصلة العائمة. وهو غير معرّف عند 0، وبالقرب من قوة للعدد عشرة قد يُقرَّب في الاتجاه الخاطئ: تكون نتيجة log10(10^15-1) هي 15 تمامًا بدقة مزدوجة. تعطي القسمة الصحيحة الإجابة الدقيقة في كل مرة.
ما هو التعقيد الزمني لعدّ الأرقام؟
يحتوي العدد n على floor(log10(n)) + 1 من الأرقام، وتُجري الحلقة عملية قسمة واحدة لكل رقم، لذا تعمل في زمن O(log n). وبالنسبة إلى عدد صحيح من 32 بت، لا يتجاوز ذلك 10 خطوات.
مسائل مشابهة
مسائل تعتمد على الأفكار نفسها. حلّ اثنتين أو ثلاث منها يثبّت النمط.
Python
def countDigits(n):
# اكتب الكود هناالحالة 1
الحالة 2
الحالة 3
المدخلات
n = 4096
المتوقع
4