Python में सरणी को समान योग वाले k उप-सरणियों में विभाजित करने की संभावना की जांच कैसे करें?

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

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

हल करने के चरण

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

उदाहरण

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