มีตัวเลข n หา Gray code ของ n (nth Gray code) Gray code เรียงเลขไบนารีที่ติดกันต่าง 1 บิต
เช่น n=12 (1100) ให้ 10 (1010)
ขั้นตอนการแก้ปัญหา
- สูตร:
gray(n) = n ^ (n >> 1)หรือแบบ Reclusive - หากำลังสอง ใหญ่สุด ≤ n เรียกว่า x
gray(n) = x + gray(2*x - n - 1)- Base case: n=0 คืน 0
ตัวอย่างโค้ด
class Solution:
def solve(self, n):
if n == 0: return 0
x = 1
while x*2 <= n: x *= 2
return x + self.solve(2*x - n - 1)
ob = Solution()
n = 12
print(ob.solve(n))
อินพุต
12
เอาต์พุต
10
