मान लीजिए कि हमारे पास दो सकारात्मक मान n और k हैं, अब हम निम्नलिखित नियमों का उपयोग करके एक बाइनरी स्ट्रिंग S_n बना सकते हैं -
-
S_1 =0
-
S_i =S_i-1 कॉन्टेनेट "1" कॉन्टेनेट रिवर्स (इनवर्ट (S_i-1)) i> 1
के लिए
यहां रिवर्स (एक्स) उलटा स्ट्रिंग एक्स देता है, और इनवर्ट (एक्स) एक्स में सभी बिट्स को फ़्लिप करता है।
ये ऐसे चार तार के उदाहरण हैं
-
S_1 ="0"
-
S_2 ="011"
-
S_3 ="0111001"
-
S_4 ="011100110110001"
हमें S_n में kth बिट खोजना है।
इसलिए, यदि इनपुट n =4 k =10 जैसा है, तो आउटपुट 1 होगा क्योंकि S_4 ="011100110110001", इसलिए 10 वां बिट 1 है (पहला बिट स्थिति 1 पर है)।
इसे हल करने के लिए, हम इन चरणों का पालन करेंगे -
-
अगर k 1 के समान है, तो
-
0 को स्ट्रिंग के रूप में लौटाएं
-
-
अन्यथा,
-
arr :=एकल तत्व 0 के साथ एक सरणी
-
arr2 :=एकल तत्व 1 के साथ एक सरणी
-
जबकि k> गिरफ्तारी का आकार, करें
-
templast :=गिरफ्तारी की प्रति
-
temp2last :=arr2 की कॉपी
-
arr :=templast concatenate 1 concatenate temp2last
-
arr2 :=templast concatenate 0 concatenate temp2last
-
-
-
गिरफ्तारी से k-1 वां तत्व लौटाएं
आइए बेहतर समझ पाने के लिए निम्नलिखित कार्यान्वयन देखें -
उदाहरण
def solve(n, k): if k == 1: return(str(0)) else: 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))
इनपुट
4, 10
आउटपुट
1