Một bữa ăn ngon có đúng hai món khác nhau với tổng độ ngon bằng một lũy thừa của hai món. Bạn có thể chọn bất kỳ hai loại thực phẩm nào khác nhau để tạo nên một bữa ăn ngon.
Giả sử chúng ta đã cho một mảng các số nguyên arr trong đó arr [i] là độ ngon của món ăn thứ i, hãy trả về số lượng các bữa ăn ngon khác nhau mà bạn có thể thực hiện từ danh sách này.
Ví dụ,
Đầu vào-1 -
arr[ ] = {1, 3, 5, 7, 9} Đầu ra -
4
Giải thích - Các bữa ăn tốt là (1,3), (1,7), (3,5) và, (7,9). Các tổng tương ứng của chúng là 4, 8, 8 và 16, tất cả đều là lũy thừa của 2.
Đầu vào-2 -
arr[ ]= {1,1,1,3,3,3,7} Đầu ra -
15
Giải thích - Bữa ăn ngon là (1,1) theo 3 cách, (1,3) theo 9 cách và (1,7) theo 3 cách.
Phương pháp được sử dụng để giải quyết vấn đề này
-
Nhận đầu vào là một mảng các số nguyên dương.
-
Một cặp đếm hàm nhận tất cả các phần tử của mảng dưới dạng danh sách các số nguyên.
-
Sắp xếp phần tử mảng đầu vào theo thứ tự tăng dần.
-
Đối với mọi phần tử của mảng, hãy tìm tổng lớn nhất sao cho mọi phần tử đều bằng '2'.
Ví dụ
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]))
Đầu ra
4