পাইথনে রান-লেংথ এনকোডেড ভেক্টরের ডট প্রোডাক্ট বের করা

দুটি রান-লেংথ এনকোডেড ভেক্টরের ডট প্রোডাক্ট বের করা হয়। উদাহরণ: [3, 1, 4, 2] মানে [1,1,1, 2,2,2,2]।

ইনপুট উদাহরণ

nums1 = [2, 7, 5, 3]  # [7,7, 3,3,3,3,3]
nums2 = [3, 5, 4, 2]  # [5,5,5, 2,2,2,2]

আউটপুট: 109

পদ্ধতি

দুই পয়েন্টার ব্যবহার করে শেষ থেকে শুরু করে কাউন্ট মিলিয়ে গুণফল যোগ করা হয়। বাকি কাউন্ট থাকে তবে সেটি পুশ ব্যাক করা হয়।

পাইথন কোড

def solve(nums1, nums2):
    ans = 0
    while nums1 and nums2:
        val1 = nums1.pop()
        count1 = nums1.pop()
        val2 = nums2.pop()
        count2 = nums2.pop()
        ans += (val1 * val2) * min(count2, count1)
        if count2 > count1:
            nums2.append(abs(count2 - count1))
            nums2.append(val2)
        elif count1 > count2:
            nums1.append(abs(count2 - count1))
            nums1.append(val1)
    return ans

# টেস্ট
nums1 = [2, 7, 5, 3]
nums2 = [3, 5, 4, 2]
print(solve(nums1, nums2))  # 109

ব্যাখ্যা

সময় জটিলতা: O(n + m) যেখানে n, m হলো এনকোডেড লিস্টের লেংথ। স্পেস: O(1) অতিরিক্ত।