जांचें कि क्या पायथन में समान योग के साथ k उप-सरणी में विभाजन करना संभव है

मान लीजिए कि हमारे पास संख्याओं की एक सरणी है जिसे अंक कहा जाता है, और एक अन्य मान K भी है। हमें यह जांचना होगा कि क्या हम सरणी संख्याओं को K सन्निहित उप-सरणी में विभाजित कर सकते हैं जैसे कि प्रत्येक उप-सरणी का तत्व योग बराबर है।

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

इसे हल करने के लिए, हम इन चरणों का पालन करेंगे -

• n :=अंकों का आकार
• cumul_sum :=अंकों में सभी तत्वों का संचयी योग
• total_sum :=cumul_sum[n - 1]
• यदि Total_sum k से विभाज्य नहीं है, तो
  • झूठी वापसी
• गिनती:=0, स्थिति:=-1
• मैं के लिए 0 से n -1 की सीमा में, करो
  • यदि स्थिति -1 के समान है, तो
    • उप:=0
  • अन्यथा,
    • उप:=cumul_sum[pos]
  • अगर cumul_sum[i] - सब (total_sum / K) के समान है, तो
    • स्थिति:=मैं
    • गिनती :=गिनती + 1
  • अन्यथा जब cumul_sum[i] - cumul_sum[pos]> (total_sum / K), तब
    • लूप से बाहर आएं
• सही लौटें जब गिनती K के समान हो, अन्यथा गलत हो

उदाहरण

आइए बेहतर समझ पाने के लिए निम्नलिखित कार्यान्वयन देखें -

def solve(nums, k):
   n = len(nums)
   cumul_sum = [0 for i in range(n)]
   cumul_sum[0] = nums[0]
   for i in range(1, n):
      cumul_sum[i] = cumul_sum[i - 1] + nums[i]
   total_sum = cumul_sum[n - 1]
   if total_sum % k != 0:
      return False
   count = 0
   pos = -1
   for i in range(n):
      if pos == -1:
         sub = 0
      else:
         sub = cumul_sum[pos]
      if cumul_sum[i] - sub == total_sum / k:
         pos = i
         count += 1
      elif cumul_sum[i] - cumul_sum[pos] > total_sum / k:
         break
   return count == k
nums = [2, 5, 3, 4, 7]
k = 3
print(solve(nums, k))

इनपुट

[2, 5, 3, 4, 7], 3

आउटपुट

True