Binary string S_n: S_1="0", S_i = S_{i-1} + "1" + reverse(invert(S_{i-1})) หา bit ที่ k ใน S_n โดยไม่สร้าง string ทั้งหมด ใช้การสร้าง array คู่ arr (S_i) และ arr2 (invert) ขยายจนความยาว >= k แล้วคืน arr[k-1]
ขั้นตอนการทำงาน
- ถ้า k == 1: คืน '0'
- arr = [0], arr2 = [1]
- while k > len(arr): templast=arr.copy(), temp2last=arr2.copy()
- arr = templast + [1] + temp2last
- arr2 = templast + [0] + temp2last
- คืน str(arr[k-1])
ตัวอย่างโค้ด
def solve(n, k):
if k == 1:
return str(0)
arr = [0]
arr2 = [1]
while k > len(arr):
templast = arr.copy()
temp2last = arr2.copy()
arr = templast + [1] + temp2last
arr2 = templast + [0] + temp2last
return str(arr[k-1])
n = 4
k = 10
print(solve(n, k)) # Output: 1
อินพุต/เอาต์พุต
Input: n=4, k=10 Output: 1
S_4 = "011100110110001", bit ที่ 10 คือ 1
