Counting Bits
يُعطى لك عدد صحيح n أكبر من أو يساوي 0. لكل عدد i من 0 إلى n، احسب عدد الـ1 الظاهرة عند كتابة i بالنظام الثنائي. أعدّ الأعداد في مصفوفة تضم n+1 مُدخلًا، حيث يكون المُدخل i هو العدد المحسوب للعدد i.
الدالة
- ninteger
- آخر رقم للعد، 0 أو أكثر
- تُرجعinteger-array
- مصفوفة من n+1 عددًا، حيث يمثّل العنصر i عدد البتات 1 في i
القيود
0 ≤ n ≤ 2 × 104
أمثلة
- المدخلات
- n = 2
- المخرجات
- [0, 1, 1]
- الشرح
- في النظام الثنائي، 0 هو
0، و1 هو1، و2 هو10. أي لا توجد وحدات، ثم وحدة واحدة، ثم وحدتان.
- المدخلات
- n = 5
- المخرجات
- [0, 1, 1, 2, 1, 2]
- الشرح
- العدد 3 هو
11والعدد 5 هو101، ولكلٍّ منهما اثنان من الرقم 1، بينما العدد 4 هو100وفيه رقم 1 واحد. وبإضافة 0 و1 و2 من المثال الأول، تكون الأعداد من 0 إلى 5 هي 0، 1، 1، 2، 1، 2.
+15 اختبارات مخفية عند الإرسال
سؤال إضافي
هل يمكنك ملء المصفوفة كاملةً بزمن O(n)، من دون استخدام دالة مدمجة تحسب عدد البتات، ومن دون حساب كل عدد من البداية؟
تلميحات
افتحها واحدًا تلو الآخر. كل تلميح يكشف أكثر قليلًا.
اكتب الأعداد من 0 إلى 8 بالنظام الثنائي، وقارن عددًا بالعدد الذي تحصل عليه عند حذف رقمه الأخير. العدد 6 هو
110والعدد 3 هو11. كيف يقارن عدد مرات ظهور الرقم 1 في كلٍّ منهما؟إن إزاحة
i >> 1إلى اليمين بمقدار خانة واحدة تحذف آخر رقم ثنائي منi. عددiيساوي عددi >> 1زائد ذلك الرقم الأخير، وهوi & 1.املأ مصفوفة تصاعديًا بدءًا من 0. عندما تصل إلى
i، يكون المدخل المقابل لـi >> 1قد مُلئ بالفعل لأنه أصغر، لذا يحتاج كل مدخل إلى عملية بحث واحدة وعملية جمع واحدة.
الحل
إن عدّ الأرقام 1 لكل عدد على حدة ينجح، لكنه يكرر العمل. العدد 13 هو 1101 والعدد 6 هو 110: بتات العدد 13 هي بتات العدد 6 مع رقم إضافي في النهاية. إذا ملأت الإجابات بترتيب تصاعدي، فسيكون العدد الذي تحتاج إليه من أجل i موجودًا بالفعل في المصفوفة، وكل خانة تتطلب عملية جمع واحدة.
احسب بتات كل عدد
الفكرة
خذ كل عدد من 0 إلى n واحسب مباشرةً عدد بتات 1 فيه. أقل بت في x هو x & 1. أضِفه إلى عدّاد، ثم أزِح x إلى اليمين باستخدام x >> 1 ليصبح البت التالي هو الأقل. توقّف عندما تصل قيمة x إلى 0.
بالنسبة إلى 13، وهو 1101، تظهر البتات من اليمين بالترتيب 1، 0، 1، 1، لذا يكون العدد 3. يتطلب كل عدد خطوة واحدة لكل رقم ثنائي، والعدد الذي لا يتجاوز n له نحو log2 n رقمًا.
وهذا يجعل زمن التنفيذ الكلي O(n log n). عندما تكون قيمة n = 2 × 10^4، يكون العدد نحو 20,000 × 15 = 300,000 خطوة، وهذا يُنفَّذ في الوقت المحدد. لكنه ما زال يهدر العمل: فحساب عدد البتات في 13 يكرر كل خطوة سبق تنفيذها عند حساب العدد 6. المساحة هي O(1)، باستثناء مصفوفة الإخراج.
الخوارزمية
- ابدأ قائمة نتائج فارغة.
- لكل
iمن 0 إلىn، اضبطcountعلى 0 وxعلىi. - طالما أن
xأكبر من 0، أضفx & 1إلىcountوأزِحxإلى اليمين بمقدار واحد. - ألحِق
countبالنتيجة. - أعِد النتيجة.
def countBits(n):
bits = []
for i in range(n + 1):
count = 0
x = i
while x > 0:
count += x & 1 # the lowest bit
x >>= 1 # shift it out
bits.append(count)
return bitsضاعف العدد
الفكرة
إزاحة i إلى اليمين بمقدار واحد تحذف آخر رقم ثنائي منه. لذا فإن i يحتوي بالضبط على بتات 1 الموجودة في i >> 1، بالإضافة إلى بت آخر عندما يكون رقمه الأخير 1. هذا الرقم الأخير هو i & 1، ما يعطينا القاعدة bits[i] = bits[i >> 1] + (i & 1).
لكل i يساوي 1 أو أكثر، تكون قيمة i >> 1 أصغر من i. إذا ملأت المصفوفة من اليسار إلى اليمين، بدءًا من bits[0] = 0، فسيكون المدخل الذي تبحث عنه معبأً بالفعل دائمًا. هذه هي البرمجة الديناميكية: تُبنى كل إجابة من إجابة أصغر.
عندما تكون قيمة n = 5: bits[1] = bits[0] + 1 = 1، bits[2] = bits[1] + 0 = 1، bits[3] = bits[1] + 1 = 2، bits[4] = bits[2] + 0 = 1، bits[5] = bits[2] + 1 = 2. يتطلب كل مدخل إزاحة واحدة وعملية AND واحدة وعملية جمع واحدة، لذا فالزمن هو O(n)، ولا حاجة إلى ذاكرة تتجاوز مساحة الإخراج.
الخوارزمية
- أنشئ مصفوفة
bitsمكوّنة منn+1أصفار. تبقىbits[0]مساويةً لـ 0. - لكل
iمن 1 إلىn، عيّنbits[i]إلىbits[i >> 1] + (i & 1). - أعِد
bits.
def countBits(n):
bits = [0] * (n + 1)
for i in range(1, n + 1):
# i >> 1 is i without its last bit, and i & 1 is that last bit
bits[i] = bits[i >> 1] + (i & 1)
return bits
أخطاء شائعة وحالات حدّية
تُكتب القاعدة في سطر واحد، لذا تختبئ الأخطاء حولها.
- تحتوي المصفوفة على
n+1من العناصر، وليسn. عندما تكونn= 0، تكون الإجابة[0]: عنصر واحد، للعدد 0. - أسبقية العمليات. في Python وC وJava وJavaScript، تكون أسبقية
+أعلى من&، لذا تُقرأbits[i >> 1] + i & 1على أنها(bits[i >> 1] + i) & 1. أبقِ الأقواس حول(i & 1). - البحث عن
bits[i-1]بدلًا منbits[i >> 1]. لا تتبع الأعداد المتجاورة قاعدة بسيطة مشتركة: فالعدد 7 هو111وفيه ثلاثة أرقام 1، والعدد 8 هو1000وفيه رقم واحد. - في Lua وR، تبدأ المصفوفات من الفهرس 1، لذا يوجد عدد
iعند الفهرسi+1، ويكون البحث عنi >> 1عند الفهرسfloor(i/2) + 1. لا يدعم Lua في بيئة التشغيل عامل الإزاحة، لذا اقسم على 2 باستخدامmath.floor(i / 2). - تحويل كل عدد إلى سلسلة ثنائية وعدّ أحرف
1يعطي الإجابة الصحيحة، لكنه ينشئ سلسلة جديدة لكل عدد.
أسئلة شائعة4
ما التعقيد الزمني لمسألة عدّ البتات؟
يعمل الحل الأفضل بزمن O(n): إذ يأتي كلٌّ من الإدخالات n+1 من إدخال سابق واحد بإجراء عملية جمع واحدة. ويستغرق حساب بتات كل عدد واحدًا تلو الآخر زمنًا قدره O(n log n)، لأن العدد الذي لا يتجاوز n يتكوّن من نحو log2 n رقمًا ثنائيًا. ويستخدم كلا الحلين ذاكرة O(1) إضافية beyond مصفوفة الإخراج.
لماذا تعمل التعليمة bits[i] = bits[i >> 1] + (i & 1)؟
i >> 1 هو i بعد حذف آخر رقم ثنائي منه، وi & 1 هو ذلك الرقم المحذوف. عدد الـ1 في i هو عدد الـ1 في العدد الأقصر زائد الرقم الأخير. بالنسبة إلى 11، وهو 1011، فالعدد الأقصر هو 5 (101، وفيه رقما 1) والرقم الأخير هو 1، لذا يحتوي 11 على ثلاثة أرقام 1.
هل توجد علاقة تكرارية أخرى بزمن O(n) لعدّ البِتّات؟
نعم. تزيل i & (i-1) أقل بت قيمته 1 في i، لذا تكون bits[i] = bits[i & (i-1)] + 1 لكل i يساوي 1 أو أكثر. بالنسبة إلى 12 (1100)، تكون 12 & 11 هي 8 (1000)، التي تحتوي على 1 واحد، لذا يحتوي 12 على اثنين. إنها سريعة بقدر قاعدة الإزاحة وتستخدم الملء نفسه من اليسار إلى اليمين.
هل يمكنني استخدام دالة مدمجة لحساب عدد البتات المضبوطة؟
تحتوي معظم لغات البرمجة على دالة كهذه، مثل Integer.bitCount في Java أو __builtin_popcount في C وC++، واستدعاؤها لكل عدد يعطي إجابة صحيحة. عادةً ما يطلب القائمون على المقابلات النسخة التي لا تستخدمها، لأن الهدف من المسألة هو إعادة استخدام الإجابات التي حسبتها بالفعل. وتعمل علاقة العودية أيضًا في اللغات التي لا تحتوي على دالة كهذه.
مسائل مشابهة
مسائل تعتمد على الأفكار نفسها. حلّ اثنتين أو ثلاث منها يثبّت النمط.
Python
def countBits(n):
# اكتب الكود هناالحالة 1
الحالة 2
المدخلات
n = 2
المتوقع
[0, 1, 1]