C++で行列内に指定した積となるペアが存在するかどうかを判定する方法

本記事では、N × M のサイズの行列と、目標となる積 K が与えられたとき、その積 K になるような2つの要素のペアが行列内に存在するかどうかを判定するアルゴリズムを解説します。

問題の概要

例として、次のような 4 × 4 の行列を考えてみましょう。

このとき、K = 42 が与えられた場合、6 × 7 = 42 となるため、ペア (6, 7) が存在することになります。

解法のアプローチ：ハッシュを活用

この問題はハッシュテーブルを使うことで効率的に解けます。基本的な考え方は以下の通りです。

1. 行列の要素を走査しながら、ハッシュセットに要素を登録していきます。
2. 現在の要素 matrix[i][j] について、K がその要素で割り切れるかどうかを確認します。
3. 割り切れる場合、商 K / matrix[i][j] がすでにハッシュセットに存在するかを調べます。
4. 存在すれば、積が K となるペアが見つかったことになります。

条件を式で表すと次のようになります。

• K % matrix[i][j] == 0(K が現在の要素で割り切れる)
• ハッシュセットに K / matrix[i][j] が含まれている

この両方が成立すれば true を返し、見つからなければ現在の要素をハッシュセットに挿入して走査を続けます。最後までペアが見つからなければ false を返します。

この手法により、全ペアを総当たりする O(N²M²) の計算量を避け、O(N × M) の時間計算量で効率的に判定できます。

C++による実装例

#include <iostream>
#include <unordered_set>
#define N 4
#define M 4
using namespace std;
bool isPairPresent(int matrix[N][M], int K) {
    unordered_set<int> s;
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < M; j++) {
            if ((K % matrix[i][j] == 0) && (s.find(K / matrix[i][j]) != s.end())) {
                return true;
            } else {
                s.insert(matrix[i][j]);
            }
        }
    }
    return false;
}
int main() {
    int matrix[N][M] = {{1, 2, 3, 4},
                        {5, 6, 7, 8},
                        {9, 10, 11, 12},
                        {13, 14, 15, 16}};
    int k = 42;
    if (isPairPresent(matrix, k) == false)
        cout << "NO PAIR EXIST";
    else
        cout << "Pair is present";
}

実行結果

Pair is present

まとめ

ハッシュセットを利用することで、行列内に積が K となるペアが存在するかどうかを線形時間で判定できます。割り算の余りチェックと商の存在確認を組み合わせるこの手法は、「和が特定値になるペアを探す」問題の積バージョンとも言える定番アルゴリズムです。ゼロ除算に注意が必要な点(行列に 0 が含まれる場合は除算前に除外する)だけ留意しておきましょう。