Giả sử chúng ta có một danh sách với các giá trị dương, được gọi là nums và cũng có một số dương k. Chúng ta phải tìm độ dài của danh sách con ngắn nhất (có thể trống) mà chúng ta có thể xóa khỏi nums, sao cho tổng các phần tử còn lại chia hết cho k. Nhưng chúng tôi không thể loại bỏ toàn bộ danh sách. Nếu không có danh sách con nào như vậy để xóa, hãy trả về -1.
Vì vậy, nếu đầu vào giống như nums =[5,8,6,3] k =8, thì đầu ra sẽ là 1, vì tổng hiện tại của các phần tử của [5,8,6,3] là 22. Nếu chúng ta loại bỏ danh sách con [6] có độ dài 1, sau đó tổng là 16, chia hết cho 8.
Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -
- rem:=(tổng tất cả các phần tử có trong nums + k) mod k
- nếu rem giống 0, thì
- trả về 0
- n:=kích thước của nums
- presum:=0
- mp:=một từ điển, ban đầu lưu trữ -1 cho khóa 0
- res:=n
- đối với tôi trong phạm vi từ 0 đến n - 1, thực hiện
- presum:=presum + nums [i]
- m:=(presum + k) mod k
- mp [m]:=i
- nếu (m - rem + k) mod k có trong mp, thì
- res:=tối thiểu của res và (i - mp [(m - rem + k) mod k])
- trả về res nếu res không giống n nếu không -1
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):
rem = (sum(nums) + k) % k
if rem == 0:
return 0
n, presum = len(nums), 0
mp = {0: -1}
res = n
for i in range(n):
presum += nums[i]
m = (presum + k) % k
mp[m] = i
if (m - rem + k) % k in mp:
res = min(res, i - mp[(m - rem + k) % k])
return res if res != n else -1
nums = [5,8,6,3]
k = 8
print(solve(nums, k)) Đầu vào
[5,8,6,3], 8
Đầu ra
1