Pythonでおいしい食事を数える

おいしい食事には、2の累乗に等しい美味しさの合計を持つちょうど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つの方法です。

この問題を解決するために使用されるアプローチ

• 入力を正の整数の配列として受け取ります。

• 関数カウントペアは、すべての配列要素を整数のリストとして受け取ります。

• 入力配列要素を昇順で並べ替えます。

• 配列のすべての要素について、すべての要素が「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