วิธีตรวจสอบว่าเลขเป็นกำลังของ d โดยที่ d เป็นกำลังของ 2 ใน Python

ปัญหา

กำหนดตัวเลข n และ x ตรวจสอบว่า n เป็นกำลังของ x หรือไม่ โดยที่ x เองเป็นกำลังของ 2

ตัวอย่าง: n = 32768, x = 32 → True เพราะ 32768 = 32³

แนวทางแก้ปัญหา

1. ตรวจสอบว่า n เป็นกำลังของ 2 (โดย n & (n-1) == 0)
2. นับจำนวนครั้งที่หาร 2 ลงตัว (cnt)
3. คำนวณเลขยกกำลังของ x (log2(x)) ผ่านฟังก์ชัน find_pow_of_2
4. ตรวจสอบว่า cnt % log2(x) == 0

ตัวอย่างโค้ด

def find_pow_of_2(n):
    return (1 + find_pow_of_2(n / 2)) if (n > 1) else 0

def solve(n, c):
    cnt = 0
    if n and (n & (n - 1)) == 0:
        while n > 1:
            n >>= 1
            cnt += 1
        return cnt % (find_pow_of_2(c)) == 0
    return False

n = 32768
x = 32
print(solve(n, x))  # True

อินพุต / เอาต์พุต

Input: 32768, 32
Output: True