Giả sử chúng ta có một mảng gọi là nums, mảng này chứa số phần tử chẵn và có giá trị khác là k. Chúng ta phải chia các số thành đúng n / 2 cặp sao cho tổng của mỗi cặp chia hết cho k. Nếu chúng ta có thể làm như vậy thì trả về true, ngược lại là false.
Vì vậy, nếu đầu vào là nums =[9,5,3,4,7,10,20,8] k =3, thì đầu ra sẽ là True vì chúng ta có thể tạo các cặp như (9,3), (5 , 7), (4,20), (8,10), tổng của tất cả các cặp chia hết cho 3.
Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -
-
dp:=một danh sách mới
-
đếm:=0
-
đối với mỗi x trong nums, thực hiện
-
t:=k - (x mod k)
-
nếu t giống với k thì
-
count:=count + 1
-
-
nếu không,
-
chèn t vào cuối dp
-
-
-
nếu số lượng mod 2 không giống 0, thì
-
trả về Sai
-
-
sắp xếp danh sách dp
-
thấp:=0
-
cao:=kích thước của dp - 1
-
trong khi thấp
-
nếu dp [low] + dp [high] không giống k thì
-
trả về Sai
-
-
thấp:=thấp + 1
-
cao:=cao - 1
-
-
trả về True
Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -
Ví dụ
def solve(nums, k): dp=[] count=0 for x in nums: t=k-(x % k) if t == k: count+=1 else: dp.append(t) if count % 2 != 0: return False dp.sort() low = 0 high = len(dp)-1 while low < high: if dp[low] + dp[high] != k: return False low += 1 high -= 1 return True nums = [9,5,3,4,7,10,20,8] k = 3 print(solve(nums, k))
Đầu vào
[9,5,3,4,7,10,20,8], 3
Đầu ra
True