পাইথনে বাইনারি লিস্টের প্রতিটি পজিশনে সব বলে মুভ করার দূরত্ব বের করা

একটি বাইনারি লিস্টে ১ মানে বল আছে। প্রতিটি পজিশন i-তে সব বল আনতে মোট দূরত্ব L[i] = Σ|j - i| (যেখানে nums[j] == 1) বের করুন।

ইনপুট উদাহরণ

nums = [1, 1, 0, 1]

আউটপুট: [4, 3, 4, 5]

অ্যালগরিদম

1. প্রথমে সব ১-এর পজিশন যোগ করে right_sum এবং কাউন্ট right_count রাখুন।
2. বাম থেকে ডানে ট্রাভার্স করুন: প্রতিটি পজিশনে left_sum + right_sum = টোটাল দূরত্ব।
3. যদি ১ পাওয়া যায়, তবে right_count--, left_count++ এবং সামান্য আপডেট করুন।

পাইথন কোড

def solve(nums):
    if not nums:
        return []
    left_count = right_count = 0
    left_sum = right_sum = 0
    result = []
    for index, num in enumerate(nums):
        if num:
            right_count += 1
            right_sum += index
    for index, num in enumerate(nums):
        result.append(left_sum + right_sum)
        if num:
            right_count -= 1
            left_count += 1
        left_sum += left_count
        right_sum -= right_count
    return result

# টেস্ট
print(solve([1, 1, 0, 1]))  # [4, 3, 4, 5]

ব্যাখ্যা

দুই পাসে O(n) টাইমে সমাধান। প্রথম পাসে ডান পাশের সব বলের ইনফো, دوم পাসে বাম পাশ আপডেট করে টোটাল বের করা হয়।