Count Digits

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

يتكوّن العدد n من floor(log10(n)) + 1 أرقام، وتُجري الحلقة عملية قسمة واحدة لكل رقم، لذا تعمل بزمن O(log n) ومساحة O(1) . وبالنسبة إلى عدد صحيح ذي 32 بت، فإن ذلك يستغرق 10 خطوات كحد أقصى.

Q: هل يمكنك استخدام log10 لعدّ أرقام عدد ما؟

لـ n موجب، يكون العدد floor(log10(n)) + 1 ، لكن يُحسَب اللوغاريتم بفاصلة عائمة. وهو غير معرّف عند 0، وبالقرب من قوة للعدد عشرة قد يُقرَّب في الاتجاه الخاطئ: تُعطي log10(10^15-1) القيمة 15 تمامًا بدقة double. القسمة الصحيحة دقيقة دائمًا.

Q: كيف تعدّ أرقام عدد سالب؟

خذ القيمة المطلقة أولًا، ثم عُدّ كالمعتاد. يحتوي String(-42) على ثلاثة أحرف لأن علامة الطرح ليست رقمًا. بالنسبة إلى أصغر عدد صحيح من 32 بت، خذ القيمة المطلقة بنوع 64 بت، لأنه لا يتسع في 32 بت.

مبتدئرياضيات ومحاكاة

+10

بما أن العدد الصحيح n غير سالب، أَعِد عدد الأرقام التي يتكوّن منها عند كتابته بالأساس 10 من دون أصفار بادئة. يُكتب الصفر على هيئة 0 واحدة، لذا يتكوّن من رقم واحد.

الدالة

countDigits(n: integer) → integer

ninteger: العدد الصحيح غير السالب المراد قياسه
تُرجعinteger: عدد الأرقام العشرية في n

القيود

0 ≤ n ≤ 2³¹-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.

سؤال إضافي

هل يمكنك عدّ الأرقام دون استخدام حلقة تُنفَّذ مرةً لكل رقم، مثلاً باستخدام بحث ثنائي بين قوى العدد عشرة؟

تلميحات

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

فُتح 0 من 3

الحل

كل قسمة صحيحة على 10 تزيل رقمًا واحدًا. احسب عدد مرات القسمة حتى يتبقى رقم واحد، ثم أضف واحدًا لذلك الرقم. تكمن الأخطاء عند الحدود: يحتوي 0 على رقم واحد، وتفشل صيغة اللوغاريتم عند 0 وقليلًا دون قوى العشرة الكبيرة.

اكتب الرقم كنص وعدّ الأحرف

الفكرة

لغتك تكتب n بالنظام العشري بالفعل. اطلب هذه السلسلة واحسب أحرفها: يصبح 4096 "4096"، أي أربعة أحرف، ويصبح 0 "0"، لذا لا يحتاج الصفر إلى حالة خاصة.

يجري التحويل عملية قسمة واحدة لكل رقم، لذا فإن الزمن والذاكرة الإضافية كلاهما O(log n)، وبحد أقصى 10 أحرف هنا.

الخوارزمية

حوّل n إلى سلسلة عشرية باستخدام دالة لا تتحول مطلقًا إلى الترميز العلمي.
احسب عدد أحرف السلسلة.
أعِد هذا العدد. بالنسبة إلى 0، تكون السلسلة هي "0"، لذا تكون الإجابة 1 من دون أي تحقق إضافي.

def countDigits(n):
    return len(str(n))

اقسم على 10 حتى يتبقى رقم واحد

الفكرة

ابدأ العد من 1 واقسم على 10 ما دام n ≥ 10، مع إضافة 1 عند كل قسمة. البدء من 1 يعني أن لكل عدد رقمًا واحدًا على الأقل، وهذا هو بالضبط الشرط الخاص بـ 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^15-1، حيث تقرّب الدقة المزدوجة اللوغاريتم إلى 15 تمامًا، فتُشير الصيغة إلى أن عدد الأرقام هو 16.
القسمة الحقيقية في JavaScript أو Lua أو PHP أو R، حيث يُبقي / على الجزء الكسري. عندئذٍ، تُنفّذ حلقة تستمر ما دام n > 0 عدد 328 مرة عند استخدام 4096. استخدم Math.floor أو math.floor أو intdiv أو %/%.
الترميز العلمي في إصدار السلسلة النصية. تكتب R القيمة as.character(1e5) على النحو "1e+05"؛ استخدم sprintf("%.0f", n). في Lua 5.3 والإصدارات الأحدث، تحتفظ tostring(4096.0) بالجزء .0؛ استخدم string.format("%d", n).

أسئلة شائعة3

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

يتكوّن العدد n من floor(log10(n)) + 1 أرقام، وتُجري الحلقة عملية قسمة واحدة لكل رقم، لذا تعمل بزمن O(log n) ومساحة O(1). وبالنسبة إلى عدد صحيح ذي 32 بت، فإن ذلك يستغرق 10 خطوات كحد أقصى.

هل يمكنك استخدام log10 لعدّ أرقام عدد ما؟

لـ n موجب، يكون العدد floor(log10(n)) + 1، لكن يُحسَب اللوغاريتم بفاصلة عائمة. وهو غير معرّف عند 0، وبالقرب من قوة للعدد عشرة قد يُقرَّب في الاتجاه الخاطئ: تُعطي log10(10^15-1) القيمة 15 تمامًا بدقة double. القسمة الصحيحة دقيقة دائمًا.

كيف تعدّ أرقام عدد سالب؟

خذ القيمة المطلقة أولًا، ثم عُدّ كالمعتاد. يحتوي String(-42) على ثلاثة أحرف لأن علامة الطرح ليست رقمًا. بالنسبة إلى أصغر عدد صحيح من 32 بت، خذ القيمة المطلقة بنوع 64 بت، لأنه لا يتسع في 32 بت.

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

اختبار #1

اختبار #2

اختبار #3

وسيط

n = 4096

الإخراج المتوقع