পাইথনে সর্ট করা সাবঅ্যারে সমের রেঞ্জ সম বের করার প্রোগ্রাম

n সংখ্যক ধনাত্মক উপাদান সম্বিষ্ট একটি nums অ্যারে দেওয়া আছে। nums-এর সকল নন-খালি সংলগ্ন সাবঅ্যারে (contiguous subarray) এর সম গণনা করে সেগুলোকে অক্রমাঅনুক্রমে (non-decreasing) সর্ট করে একটি নতুন অ্যারে তৈরি করা হয়, যার আকার n×(n+1)/2। এই নতুন অ্যারেতে left থেকে right ইনডেক্স পর্যন্ত (১-ভিত্তিক) উপাদানগুলোর সম বের করতে হবে। ফলাফল বড় হতে পারে, তাই ১০⁹ + ৭ দিয়ে মডুলো ফেরত দিতে হবে।

যেমন, nums = [1,5,2,6], left = 1, right = 5 হলে আউটপুট ২০। কারণ সব সাবঅ্যারে সম: 1, 5, 2, 6, 6, 7, 8, 8, 13, 14। সর্ট করার পর: [1,2,5,6,6,7,8,8,13,14]। ১ থেকে ৫ নম্বর ইনডেক্স পর্যন্ত সম = 1+2+5+6+6 = ২০।

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

m := 10⁹ + 7
n := nums-এর আকার
a := একটি খালি লিস্ট
i = 0 থেকে n-1 পর্যন্ত লুপ:

j = i থেকে n-1 পর্যন্ত লুপ:

যদি i == j হয়, তবে nums[j] কে a-তে যোগ করুন।
অন্যথায়, (nums[j] + a-এর শেষ উপাদান) mod m কে a-তে যোগ করুন।

a সর্ট করুন।
sm := a[left-1 : right] এর উপাদানগুলোর সম।
sm mod m ফেরত দিন।

উদাহরণ

def solve(nums, left, right):
    m = 10**9 + 7
    n = len(nums)
    a = []
    for i in range(n):
        for j in range(i, n):
            if i == j:
                a.append(nums[j])
            else:
                a.append((nums[j] + a[-1]) % m)
    a.sort()
    sm = sum(a[left-1:right])
    return sm % m

nums = [1,5,2,6]
left = 1
right = 5
print(solve(nums, left, right))

ইনপুট

[1,5,2,6], 1, 5