همان‌طورکه می‌دانید یکی از مشکلاتی که در برنامه نویسی وجود دارد، عدم توانایی کامپیوتر در نگه‌داری متغیّرهای یک بیتی است. در این مسئله یک آرایه به نام ‎$a$‎ با اندازه ‎$\lceil\frac{n}{8}\rceil$‎ از نوع ‎char‎ به شما داده شده است. می‌توانید فرض کنید که همه‌ی عناصر ‎$a$‎ در ابتدا صفر هستند. شما بایستی بدون استفاده از هیچ آرایه‌ی اضافی توابع زیر را بنویسید که بتوانند ‎$n$‎ متغیر ‎$1$‎ بیتی از ‎$0$‎ تا ‎$n-1$‎ را ذخیره کنند یا مقدار ذخیره شده را باز گردانند (در ابتدا همه‌ی متغیّرها صفر هستند):

1. تابع ‎void set(int i‎, ‎bool x)‎ این تابع مقدار متغیّر ‎$i$‎ام ‎($0\leq i < n$)‎ را ‎$x$‎ قرار می‌دهد. زمان این تابع باید از ‎$O(1)$‎ باشد.
2. تابع bool get(int i)‎ این تابع مقدار متغیّر ‎$i$‎ام را بر می‌گرداند. زمان این تابع باید از ‎$O(1)$‎ باشد.

• سوال بعد
• سوال قبل