ตรวจสอบว่าอาร์เรย์สามารถแบ่งออกเป็นคู่ที่ผลรวมหารด้วย k ใน Python . ลงตัวหรือไม่

สมมติว่าเรามีอาร์เรย์ของตัวเลขและมีตัวเลข k อีกตัวหนึ่ง เราต้องตรวจสอบว่าอาร์เรย์ที่กำหนดสามารถแบ่งออกเป็นคู่ได้หรือไม่ เพื่อให้ผลรวมของทุกคู่หารด้วย k ลงตัวหรือไม่

ดังนั้น หากอินพุตเป็นเหมือน arr =[5, 15, 6, 9] k =7 ผลลัพธ์จะเป็น True เนื่องจากเราสามารถจับคู่ (5, 9) และ (15, 6) ได้

เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -

• n :=ขนาดของอาร์เรย์
• ถ้า n เป็นเลขคี่ ดังนั้น
  • คืนค่าเท็จ
• เหตุการณ์ :=พจนานุกรมว่างเปล่า หากไม่มีคีย์บางคีย์ คืนค่า 0 เป็นค่าของคีย์ที่หายไปนั้น
• สำหรับ i ในช่วง 0 ถึง n ให้ทำ
  • เพิ่มจำนวนครั้ง[((array[i] mod k) + k) mod k] 1
• สำหรับ i ในช่วง 0 ถึง n ให้ทำ
  • ที่เหลือ :=((array[i] mod k) + k) mod k
  • ถ้า 2 * เศษเหลือเท่ากับ k แล้ว
    • หากเหตุการณ์[ที่เหลือ] เป็นเลขคี่
      • คืนค่าเท็จ
  • มิฉะนั้น เมื่อเศษเหลือเท่ากับ 0 แล้ว
    • ถ้าเหตุการณ์[เหลือ] AND 1 ไม่ใช่ศูนย์ ดังนั้น
      • คืนค่าเท็จ
  • มิฉะนั้น เมื่อเหตุการณ์[ที่เหลือ] ไม่เหมือนกับเหตุการณ์[k - ส่วนที่เหลือ] แล้ว
    • คืนค่าเท็จ
• คืนค่า True

ให้เราดูการใช้งานต่อไปนี้เพื่อความเข้าใจที่ดีขึ้น -

ตัวอย่าง

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))

อินพุต

[5, 15, 6, 9], 7

ผลลัพธ์

True