همانطورکه میدانید یکی از مشکلاتی که در برنامه نویسی وجود دارد، عدم توانایی کامپیوتر در نگهداری متغیّرهای یک بیتی است. در این مسئله یک آرایه به نام a با اندازه ⌈n8⌉ از نوع char به شما داده شده است. میتوانید فرض کنید که همهی عناصر a در ابتدا صفر هستند. شما بایستی بدون استفاده از هیچ آرایهی اضافی توابع زیر را بنویسید که بتوانند n متغیر 1 بیتی از 0 تا n−1 را ذخیره کنند یا مقدار ذخیره شده را باز گردانند (در ابتدا همهی متغیّرها صفر هستند):
void set(int i, bool x)
این تابع مقدار متغیّر iام (0≤i<n) را x قرار میدهد. زمان این تابع باید از O(1) باشد.bool get(int i)
این تابع مقدار متغیّر iام را بر میگرداند. زمان این تابع باید از O(1) باشد.