Kiểm tra xem có thể phân vùng trong k mảng con với tổng bằng nhau trong Python hay không

Giả sử chúng ta có một mảng số được gọi là nums và cũng có một giá trị khác là K. Chúng ta phải kiểm tra xem chúng ta có thể phân chia mảng num thành K mảng con liền nhau sao cho tổng phần tử của mỗi mảng con bằng nhau.

Vì vậy, nếu đầu vào là nums =[2, 5, 3, 4, 7] k =3, thì đầu ra sẽ là True vì chúng ta có thể tạo ba phân vùng như [(2, 5), (3, 4), (7)] tất cả đều có tổng bằng nhau 7.

Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -

• n:=kích thước của nums
• cumul_sum:=tổng tích lũy của tất cả các phần tử tính bằng nums
• total_sum:=cumul_sum [n - 1]
• nếu tổng_sum không chia hết cho k, thì
  • trả về Sai
• count:=0, pos:=-1
• đối với tôi trong phạm vi từ 0 đến n - 1, thực hiện
  • nếu pos giống -1, thì
    • phụ:=0
  • nếu không,
    • sub:=cumul_sum [pos]
  • nếu cumul_sum [i] - sub giống như (total_sum / K), thì
    • pos:=i
    • count:=count + 1
  • ngược lại khi cumul_sum [i] - cumul_sum [pos]> (total_sum / K), thì
    • ra khỏi vòng lặp
• trả về true khi số đếm giống K, ngược lại là false

Ví dụ

Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -

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))

Đầu vào

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

Đầu ra

True