पायथन का उपयोग करके सॉर्ट किए गए सबएरे सम के रेंज सम को खोजने का प्रोग्राम

मान लीजिए हमारे पास n सकारात्मक तत्वों वाली एक सरणी nums है। यदि हम nums के सभी गैर-खाली सन्निहित सबएरे के योग की गणना करते हैं और फिर उन्हें गैर-घटते क्रम में सॉर्ट करते हैं, जिससे n*(n+1)/2 संख्याओं की एक नई सरणी बनती है। हमें नई सरणी में इंडेक्स left से इंडेक्स right (1-इंडेक्स्ड) तक की संख्याओं का योग ढूंढना है, समावेशी। उत्तर बहुत बड़ा हो सकता है इसलिए परिणाम को 10^9 + 7 से मोडुलो वापस करें।

उदाहरण के लिए, यदि इनपुट nums = [1,5,2,6] left = 1 right = 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 := 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