【C++】合計がSかつXORがKとなる正の整数の順序対をカウントする方法

2つの整数 S(合計)と K(XOR)が与えられたとき、「合計が S になり、XOR(排他的論理和)が K になる正の整数の順序対」がいくつ存在するかを求めるのが、この問題のゴールです。

ここでいう順序対(ordered pair)とは、(i, j) と (j, i) を互いに異なるペアとして区別して数えることを意味します。そのため、同じ2つの数の組み合わせでも、並び順が違えば別々にカウントされます。

問題を解く基本的な考え方

アプローチはとてもシンプルです。i を 1 から順に動かしながら、各 i に対して j = i + 1 以降の値を順番に試していきます。そして、ペア (i, j) が次の2つの条件を同時に満たすかどうかを確認します。

• i + j == S(合計が S に一致する)

• i ^ j == K(XOR が K に一致する)

両方の条件を満たすペアが見つかったら、count を 2 増やします。(i, j) と (j, i) のどちらも有効な順序対としてカウントされるためです。

入力例と出力例

例1: 条件を満たすペアが存在する場合

入力

S = 10, K = 4

出力

合計がSかつXORがKとなる順序対の数: 2

説明

条件を満たすのは (3, 7) と (7, 3) の2組

例2: 条件を満たすペアが存在しない場合

入力

S = 12, K = 6

出力

合計がSかつXORがKとなる順序対の数: 0

説明

条件を満たすペアは1つも存在しない

プログラムのアルゴリズム

• 整数 S と K を受け取ります。

• 関数 sumXOR(int s, int k) は、引数として受け取った s と k をもとに、「合計が s かつ XOR が k」となる順序対の個数を返します。

• カウント用の変数 count を 0 で初期化します。

• すべてのペアを列挙できるよう、二重の for ループで走査します。

• 外側のループは i = 1 から i < s まで、内側のループは j = i + 1 から j < s - 1 まで回します。

• 各ペア (i, j) に対して「(i + j == s) かつ ((i ^ j) == k)」が成立するかを判定します。成立する場合は、(i, j) と (j, i) を別々の順序対として数えるため、count を 2 増やします。

• すべてのループが終了した時点で、count には条件を満たす順序対の総数が格納されています。

• 最後に count を結果として返します。

C++での実装例

#include <bits/stdc++.h>
using namespace std;
int sumXOR(int s, int k){
    int count = 0;
    for (int i = 1; i < s; i++){
       for(int j=i+1; j<s-1; j++){
          if( (i+j)==s && (i^j)==k){
            count+=2; //(i,j) と (j,i) はそれぞれ別の順序対としてカウント
          }
       }
    }
    return count;
}
int main(){
    int S = 9, K = 5;
    cout <<"合計がSかつXORがKとなる順序対の数: "<< sumXOR(S,K);
    return 0;
}

実行結果

上記のコードを実行すると、次の出力が得られます。

合計がSかつXORがKとなる順序対の数: 4

このケース(S = 9、K = 5)では、条件を満たす組み合わせは (2, 7) と (3, 6) です。順序対として数えるため、(2, 7)(7, 2)(3, 6)(6, 3) の4組となり、出力は 4 になります。

補足: 計算量を意識した改良のヒント

この素朴な全探索の計算量は O(S²) です。S が大きくなると処理時間が伸びるため、効率化したい場合はビット演算の性質を活用できます。任意の整数 x, y に対して、次の恒等式が常に成り立ちます。

x + y = (x ^ y) + 2 * (x & y)

これを今回の条件に当てはめると、x & y = (S − K) / 2 が導かれます。つまり、S − K が負または奇数の場合は解が存在しないため、ループに入る前に即座に 0 を返せます。さらに、内側のループで j = S − i と固定して i & j だけを検証すれば、ループを1重にでき、計算量を O(S) まで抑えられるのです。