Pythonの範囲内のXORとのペアをカウントするプログラム

配列numsがあり、2つの値lとrがあるとすると、適切なペアの数を見つける必要があります。ここで、適切なペアはペア（i、j）です。ここで、0 <=i

したがって、入力がnums =[4,1,7,2] l =2 r =6のような場合、ナイスペアは（1,0）であるため、出力は6になります。1XOR 4 =5、（1 、2）：1 XOR 7 =6、（1,3）：1 XOR 2 =3、（0,3）：4 XOR 2 =6、（0,2）：4 XOR 7 =3、（2,3 ）：7 XOR2=5。

これを解決するには、次の手順に従います-

• 関数test（）を定義します。これにはnums、x

  が必要です

• count：=nums単位の要素の頻度を含むマップ

• res：=0

• xがゼロ以外の場合、実行

  • xが奇数の場合、

    • res：=res +（count [a] * count [（x-1）XOR a）のすべての要素の合計（カウント内のすべてのa）

  • count：=キーa / 2と値を使用したマップ（count [a] + count [a XOR 1] for all a in count

  • x =x/2の商

• res/2の商を返す

• メインメソッドからreturntest（nums、r + 1）-test（nums、l）

例

理解を深めるために、次の実装を見てみましょう

from collections import Counter
def solve(nums, l, r):
   def test(nums, x):
      count = Counter(nums)
      res = 0
      while x:
         if x & 1:
            res += sum(count[a] * count[(x - 1) ^ a] for a in count)
         count = Counter({a >> 1: count[a] + count[a ^ 1] for a in count})
         x >>= 1
      return res // 2

   return test(nums, r + 1) - test(nums, l)

nums = [4,1,7,2]
l = 2
r = 6
print(solve(nums, l, r))

入力

[4,1,7,2], 2, 6

出力

6