মান লাগিয়ে, আমাদের দুটি পজিটিভ মান n এবং k আছে, এখন আমরা S_n নামে একটি বাইনারি স্ট্রিং নিচের নিয়মগুলো ব্যবহার করে বানাতে পারি:
- S_1 = 0
- S_i = S_{i-1} + "1" + reverse(invert(S_{i-1})) for i > 1
এখানে reverse(x) স্ট্রিং x-কে রিভার্স করে, এবং invert(x) সব বিট ফ্লিপ করে।
এরকম চারটি স্ট্রিং এর উদাহরণ:
- S_1 = "0"
- S_2 = "011"
- S_3 = "0111001"
- S_4 = "011100110110001"
আমাদের S_n-এ k-তম বিট বের করতে হবে।
যেমন, ইনপুট n = 4, k = 10 হলে, আউটপুট হবে 1 কারণ S_4 = "011100110110001", তাই ১০তম বিট হল ১ (প্রথম বিট পজিশন ১-এ)।
এটি সমাধান করতে আমরা নিচের ধাপগুলো অনুসরণ করব:
- যদি k == 1 হয়, তবে "0" রিটার্ন করুন
- অন্যথায়:
- arr := [0] ধারণকারী একটি অ্যারে
- arr2 := [1] ধারণকারী একটি অ্যারে
- k > len(arr) থাকা পর্যন্ত:
- templast := arr-এর কপি
- temp2last := arr2-এর কপি
- arr := templast + [1] + temp2last
- arr2 := templast + [0] + temp2last
- 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
