ধরুন আমাদের দুটি ধনাত্মক মান আছে n এবং k, এখন আমরা নিম্নলিখিত নিয়মগুলি ব্যবহার করে একটি বাইনারি স্ট্রিং S_n তৈরি করতে পারি -
-
S_1 =0
-
S_i =S_i-1 concatenate "1" concatenate reverse(invert(S_i-1)) i> 1
এর জন্য
এখানে বিপরীত (x) বিপরীত স্ট্রিং x প্রদান করে, এবং উল্টানো(x) x-এ সমস্ত বিট ফ্লিপ করে।
এগুলি হল এই ধরনের চারটি স্ট্রিংয়ের উদাহরণ
-
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> arr এর আকার, do
-
টেমপ্লাস্ট :=arr এর অনুলিপি
-
temp2last :=arr2 এর কপি
-
arr :=টেমপ্লাস্ট কনক্যাটেনেট 1 কনক্যাটেনেট টেম্প2লাস্ট
-
arr2 :=টেমপ্লাস্ট কনক্যাটেনেট 0 কনক্যাটেনেট টেম্প2লাস্ট
-
-
-
arr
থেকে 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
