पायथन में K प्रीफिक्स

मान लीजिए हमारे पास संख्याओं की एक सूची nums और एक पूर्णांक k है, हमें अधिकतम संभव i ढूंढना है जहां nums[0] + nums[1] + ... + nums[i] <= k। यदि कोई वैध i मौजूद नहीं है तो -1 लौटाएंगे।

उदाहरण के लिए, यदि इनपुट है nums = [4, -7, 5, 2, 6], k = 5, तो आउटपुट होगा 3, इंडेक्स 3 है क्योंकि यदि हम 4+(-7)+5+2 = 4 जोड़ते हैं, यह k से कम है, यदि हम अंतिम तत्व जोड़ते हैं तो यह अब k से कम नहीं रहेगा, इसलिए इंडेक्स 3 है।

हल करने के चरण

• i को 1 से nums के आकार - 1 तक:
  • nums[i] := nums[i] + nums[i-1] (प्रीफिक्स योग)।
• i को nums के आकार -1 से -1 तक, 1 से घटाते हुए:
  • यदि nums[i] <= k, तो i लौटाएं।
• -1 लौटाएं।

उदाहरण

class Solution:
    def solve(self, nums, k):
        for i in range(1, len(nums)):
            nums[i] += nums[i-1]
        for i in range(len(nums)-1, -1, -1):
            if nums[i] <= k:
                return i
        return -1

ob = Solution()
nums = [4, -7, 5, 2, 6]
k = 5
print(ob.solve(nums, k))

इनपुट

[4, -7, 5, 2, 6], 5

आउटपुट

3