পাইথনে প্রথম N প্রাকৃতিক সংখ্যার পারমুটেশন থেকে মেডিয়ান M হয় এমন সাবঅ্যারে গণনা করুন

সমস্যা বিবরণ

প্রথম N প্রাকৃতিক সংখ্যার একটি পারমুটেশন অ্যারে A এবং একটি সংখ্যা M (<= N) দেওয়া আছে। মেডিয়ান M হয় এমন সাবঅ্যারে সংখ্যা বের করতে হবে। মেডিয়ান বলতে সর্টেড সিকোয়েন্সের মাঝপথের উপাদান (জোড় দৈর্ঘ্যে বামপাশের মাঝপথি)।

উদাহরণস্বরূপ, A=[3,5,6,4,2], M=5 হলে আউটপুট 4 (সাবঅ্যারে: [3,5,6], [5], [5,6], [5,6,4])।

সমাধানের ধাপসমূহ

1. my_map = {0:1}, has=False, add=0, result=0।
2. প্রতিটি উপাদান arr[i] এর জন্য:
   • যদি arr[i] < m, add--।
   • যদি arr[i] > m, add++।
   • যদি arr[i] == m, has=True।
   • যদি has হয়:
     • result += my_map.get(add, 0)।
     • result += my_map.get(add-1, 0)।
   • অন্যথায় my_map[add] = my_map.get(add,0) + 1।
3. result রিটার্ন করুন।

পাইথন কোড উদাহরণ

def solve(arr, m):
    n = len(arr)
    my_map = {0: 1}
    has = False
    add = 0
    result = 0
    for i in range(n):
        if arr[i] < m:
            add -= 1
        elif arr[i] > m:
            add += 1
        if arr[i] == m:
            has = True
        if has:
            if add in my_map:
                result += my_map[add]
            if add - 1 in my_map:
                result += my_map[add - 1]
        else:
            my_map[add] = my_map.get(add, 0) + 1
    return result

arr = [3, 5, 6, 4, 2]
m = 5
print(solve(arr, m))  # আউটপুট: 4 (নোট: আর্টিকেলে 3 লেখা আছে, কিন্তু সঠিক ৪)

ইনপুট

[3, 5, 6, 4, 2] , 5

আউটপুট

4