Giả sử chúng ta có một nums mảng và một giá trị khác p, chúng ta loại bỏ mảng con nhỏ nhất (không phải toàn bộ mảng) sao cho tổng các giá trị còn lại chia hết cho p. Chúng ta phải tìm độ dài của mảng con nhỏ nhất mà chúng ta cần loại bỏ, nếu không có mảng con nào như vậy thì trả về -1.
Vì vậy, nếu đầu vào là nums =[8,2,6,5,3] p =7, thì đầu ra sẽ là 1 vì nếu chúng ta loại bỏ 3, thì tổng sẽ là 21 và đó chia hết cho 7.
Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -
- ans:=infinity
- s:=(tổng tất cả các phần tử tính bằng nums) mod p
- d:=một bản đồ chứa cặp khóa-giá trị {0:-1}
- kiêm:=0
- nếu s giống 0, thì
- trả về 0
- đối với tôi trong phạm vi từ 0 đến kích thước của nums, hãy thực hiện
- cum:=cum + nums [i]
- r:=kiêm mod p
- nếu (r-s) mod p có trong d, thì
- ans:=tối thiểu ans và i - d [(r-s) mod p]
- d [r]:=i
- trả về ans nếu ans
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, p):
ans = float("inf")
s = sum(nums) % p
d = {0:-1}
cum = 0
if s == 0:
return 0
for i in range(len(nums)):
cum+=nums[i]
r = cum%p
if (r-s)%p in d:
ans = min(ans, i-d[(r-s)%p])
d[r] = i
return ans if ans<len(nums) else -1
nums = [8,2,6,5,3]
p = 7
print(solve(nums, p)) Đầu vào
[8,2,6,5,3], 7
Đầu ra
1