좋은 식사에는 맛의 합이 2의 거듭제곱과 같은 정확히 두 가지 다른 음식 항목이 포함됩니다. 두 가지 다른 음식을 선택하여 좋은 식사를 만들 수 있습니다.
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가지 방법입니다.
이 문제를 해결하기 위해 사용된 접근 방식
-
양의 정수 배열로 입력을 받습니다.
-
함수 카운트 쌍은 모든 배열 요소를 정수 목록으로 사용합니다.
-
입력 배열 요소를 오름차순으로 정렬합니다.
-
배열의 모든 요소에 대해 모든 요소가 '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