โจทย์
ตัดสินใจว่า n เท่ากับ 2ᵏ สำหรับจำนวนเต็มไม่ติดลบ k ใด ๆ หรือไม่ (1, 2, 4, 8, …)
ให้เขียนฟังก์ชัน is_power_of_two(n)
อินพุต
n: ตัวเลขที่ต้องการตรวจสอบ
เอาต์พุต
คืนค่า true หาก n เป็นกำลังสองของสอง
เงื่อนไข
-10¹⁸ ≤ n ≤ 10¹⁸
ตัวอย่าง
ตัวอย่างที่ 1
อินพุต:
n = 64
ผลลัพธ์ที่คาดหวัง:
expected = Trueอินพุต:
long long n = 64;
ผลลัพธ์ที่คาดหวัง:
bool expected = true;อินพุต:
long n = 64;
ผลลัพธ์ที่คาดหวัง:
bool expected = true;คำอธิบาย
64 = 2⁶
ตัวอย่างที่ 2
อินพุต:
n = 12
ผลลัพธ์ที่คาดหวัง:
expected = Falseอินพุต:
long long n = 12;
ผลลัพธ์ที่คาดหวัง:
bool expected = false;อินพุต:
long n = 12;
ผลลัพธ์ที่คาดหวัง:
bool expected = false;คำอธิบาย
12 = 4 × 3 มีตัวประกอบคี่ จึงไม่ใช่กำลังสองของสอง
แนวทางการแก้
ลองทำเองก่อน แล้วค่อยเปิดคำใบ้ทีละข้อ
คำใบ้ 1
กำลังของ 2 จะมีบิตที่เป็น 1 เพียงตัวเดียวใน binary
คำใบ้ 2
เช็กก่อนว่าจำนวนนั้นเป็นบวก แล้วค่อยใช้การทดสอบด้วยบิต
คำใบ้ 3
จำนวนลบและศูนย์ไม่ใช่กำลังของ 2
ความซับซ้อนที่คาดหวัง
เวลา O(1), หน่วยความจำเพิ่ม O(1)
แหล่งอ้างอิง
โจทย์นี้ปรับให้เหมาะกับ CodeUtility กรุณาทำตามคำชี้แจงและข้อจำกัดด้านบน