Kiểm tra xem một mảng có thể được chia thành các cặp có tổng chia hết cho k trong Python hay không

Giả sử chúng ta có một mảng số và có một số khác k, chúng ta phải kiểm tra xem mảng đã cho có thể được chia thành các cặp sao cho tổng của mọi cặp có chia hết cho k hay không.

Vì vậy, nếu đầu vào là arr =[5, 15, 6, 9] k =7, thì đầu ra sẽ là True vì chúng ta có thể lấy các cặp như (5, 9) và (15, 6).

Để 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 mảng
• nếu n lẻ, thì
  • trả về Sai
• xuất hiện:=một từ điển trống, nếu không có khóa nào đó thì trả về 0 là giá trị của khóa bị thiếu đó
• đối với tôi trong phạm vi từ 0 đến n, thực hiện
  • tăng số lần xuất hiện [((array [i] mod k) + k) mod k] lên 1
• đối với tôi trong phạm vi từ 0 đến n, thực hiện
  • phần còn lại:=((array [i] mod k) + k) mod k
  • nếu phần dư 2 * giống với k, thì
    • nếu số lần xuất hiện [phần còn lại] là lẻ, thì
      • trả về Sai
  • ngược lại khi phần còn lại bằng 0, thì
    • nếu số lần xuất hiện [phần còn lại] VÀ 1 khác 0, thì
      • trả về Sai
  • ngược lại, khi số lần xuất hiện [phần dư] không giống với số lần xuất hiện [k - phần còn lại], thì
    • trả về Sai
• 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ụ

from collections import defaultdict
def solve(array, k):
   n = len(array)
   if n % 2 != 0:
      return False
   occurrences = defaultdict(lambda : 0)
   for i in range(0, n):
      occurrences[((array[i] % k) + k) % k] += 1
   for i in range(0, n):
      remainder = ((array[i] % k) + k) % k
      if (2 * remainder == k):
         if (occurrences[remainder] % 2 != 0):
            return False
      elif (remainder == 0):
         if (occurrences[remainder] & 1):
            return False
         elif (occurrences[remainder] != occurrences[k - remainder]):
            return False
   return True
arr = [5, 15, 6, 9]
k = 7
print(solve(arr, k))

Đầu vào

[5, 15, 6, 9], 7

Đầu ra

True