Chương trình tìm số dãy con liên tiếp có tổng chia hết cho k trong Python

Giả sử chúng ta có một số mảng và một giá trị k. Chúng ta phải tìm số dãy con liên tiếp có tổng chia hết cho k.

Vì vậy, nếu đầu vào là k =3 nums =[1,2,3,4,1], thì đầu ra sẽ là 4 vì các dãy con là [3], [1,2], [1,2,3 ] và [2,3,4].

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

• x:=Một mảng có kích thước k và điền bằng 0
• x [0]:=1
• r:=0, s:=0
• đối với mỗi độ tuổi tính bằng số, hãy thực hiện
  • s:=(s + elem) mod k
  • r:=r + x [s]
  • x [s]:=x [s] + 1
• trả về r

Ví dụ

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

def solve(k, nums):
   x = [0]*k
   x[0] = 1
   r=s=0
   for elem in nums:
      s = (s+elem) % k
      r += x[s]
      x[s] += 1
   return r

k = 3
nums = [1,2,3,4,1]
print(solve(k, nums))

Đầu vào

3, [1,2,3,4,1]

Đầu ra

4