นับ Good Meals ใน Python

มื้ออาหารที่ดี (Good Meal) ประกอบด้วยรายการอาหาร 2 รายการที่ต่างกัน ซึ่งผลรวมของความอร่อย (deliciousness) เท่ากับกำลังของ 2 คุณสามารถเลือกอาหาร 2 รายการที่ต่างกันเพื่อทำมื้ออาหารที่ดีได้

สมมติเรามีอาร์เรย์ของจำนวนเต็ม arr โดยที่ arr[i] คือความอร่อยของรายการอาหารที่ i ให้คืนจำนวนมื้ออาหารที่ดีที่แตกต่างกันที่คุณสามารถทำได้จากรายการนี้

ตัวอย่าง

อินพุต-1 -

arr[ ] = {1, 3, 5, 7, 9}

เอาต์พุต -

4

คำอธิบาย - มื้ออาหารที่ดีคือ (1,3), (1,7), (3,5) และ (7,9) ผลรวมของแต่ละคู่คือ 4, 8, 8, และ 16 ซึ่งทั้งหมดเป็นกำลังของ 2

อินพุต-2 -

arr[ ]= {1,1,1,3,3,3,7}

เอาต์พุต -

15

คำอธิบาย - มื้ออาหารที่ดีคือ (1,1) 3 วิธี, (1,3) 9 วิธี, และ (1,7) 3 วิธี

แนวทางที่ใช้แก้ปัญหา

• รับอินพุตเป็นอาร์เรย์ของจำนวนเต็มบวก

• ฟังก์ชัน count pairs รับสมาชิกอาร์เรย์ทั้งหมดเป็นลิสต์ของจำนวนเต็ม

• จัดเรียงอินพุตอาร์เรย์ตามลำดับเพิ่มขึ้น

• สำหรับทุกสมาชิกของอาร์เรย์ หาผลรวมสูงสุดที่ทำให้ทุกสมาชิกเป็นกำลังของ '2'

ตัวอย่าง

class Solution:
    def countpairs(self, arr: List[int]) -> int:
        """
        elem1 + elem2 == 1 << i
        elem1 = 2 << i - elem2
        """
        result = 0
        seen = defaultdict(int)
        arr.sort()
        for d in arr:
            n = 1
            while n <= d + d:
                ans = (ans + seen[n-d]) % (10 ** 9 + 7)
                n = n << 1
            seen[d] += 1
        return ans
sol1= Solution()
print(sol1.countpairs([1,1,1,3,3,3,7]))

ผลลัพธ์

4