โปรแกรมตรวจสอบว่ารายการสามารถแบ่งพาร์ติชั่นเป็นคู่ได้หรือไม่ โดยที่ sum เป็นทวีคูณของ k ใน python

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

ดังนั้น หากอินพุตมีค่าเท่ากับ nums =[4, 7, 2, 5] k =6 เอาต์พุตจะเป็น True เนื่องจากเราสามารถแบ่งรายการที่กำหนดออกเป็นคู่ๆ เช่น (4, 2) และ (8, 1) และผลรวมหารด้วย 3 ลงตัว

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

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

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

ตัวอย่าง

class Solution:
   def solve(self, nums, k):
      if len(nums) % 2:
         return False

      count = [0] * k
      for n in nums:
         count[n % k] += 1

      if count[0] % 2:
         return False

      for i in range(1, k // 2 + 1):
         if count[i] != count[k - i]:
            return False
      return True

ob = Solution()
nums = [4, 7, 2, 5]
k = 6
print(ob.solve(nums, k))

อินพุต

[4, 7, 2, 5], 6

ผลลัพธ์

True