পাইথন ব্যবহার করে সাজানো সাবয়ারের যোগফলের পরিসরের যোগফল খুঁজে বের করার প্রোগ্রাম

ধরুন আমাদের n পজিটিভ উপাদান সহ একটি অ্যারে সংখ্যা আছে। যদি আমরা n*(n+1)/2 সংখ্যার একটি নতুন অ্যারে তৈরি করে সংখ্যার সমস্ত অ-খালি সংলগ্ন সাবয়ারের যোগফল গণনা করি এবং তারপরে তাদের অ-হ্রাস না করে সাজাই। আমাদেরকে নতুন অ্যারেতে ইনডেক্স বাম থেকে ইনডেক্স ডানে (1-ইনডেক্সড), ইনক্লুসিভ সংখ্যার যোগফল খুঁজে বের করতে হবে। উত্তরটি অনেক বড় হতে পারে তাই ফলাফল মডিউল 10^9 + 7 ফেরত দিন।

সুতরাং, যদি ইনপুটটি সংখ্যার মত হয় =[1,5,2,6] বাম =1 ডান =5, তাহলে আউটপুট হবে 20 কারণ এখানে সমস্ত সাবয়ারের যোগফল 1, 5, 2, 6, 6, 7, 8। , 8, 13, 14, তাই সাজানোর পরে, তারা হল [1,2,5,6,6,7,8,8,13,14], সূচক 1 থেকে 5 পর্যন্ত উপাদানগুলির যোগফল হল 1+5+2 +6+6 =20।

এটি সমাধান করতে, আমরা এই পদক্ষেপগুলি অনুসরণ করব -

m :=10^9 + 7
n :=সংখ্যার আকার
a:=একটি নতুন তালিকা
আমি 0 থেকে n - 1 রেঞ্জের জন্য, করুন
- j-এর জন্য i থেকে n - 1 পরিসরে, do
  - যদি আমি j এর মত হয়, তাহলে
    - একটি
  - অন্যথায়,
    - a
      এর শেষে ((nums[j] + a) mod m এর শেষ উপাদান) সন্নিবেশ করুন
তালিকাটি একটি
সাজান
sm:=a[সূচী বাম-1 থেকে ডানে])
এর সমস্ত উপাদানের যোগফল
ফিরুন 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