Python से n-वें बाइनरी स्ट्रिंग में K-वां बिट कैसे ढूंढें?

रिकर्सिव नियम S₁=0, Sᵢ=Sᵢ₋₁ + "1" + reverse(invert(Sᵢ₋₁)) से बाइनरी स्ट्रिंग बनाकर K-वां बिट ढूंढें।

एल्गोरिदम

• अगर k=1 तो '0' रिटर्न।
• दो ऐरे arr (0 से शुरू) और arr2 (1 से शुरू) मेंटेन करें।
• जब तक k > len(arr): दोनों ऐरे एक्सपैंड करें: arr = arr + [1] + arr2, arr2 = arr + [0] + arr2।
• 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 -> S₄="011100110110001", 10वां बिट = 1

इनपुट/आउटपुट

इनपुट: n=4, k=10
आउटपुट: 1