C++で連結リスト内に積がKになるペアが存在するかを判定する方法

問題の概要

要素の集合と目標となる積 K が与えられたとき、連結リスト内に「積が K と等しくなる2つの数値」が存在するかどうかを判定します。該当するペアが1つだけならそれを出力し、複数存在する場合はいずれか1つを出力すればよいものとします。

たとえば、連結リストが {2, 4, 8, 12, 15} で K = 16 の場合、2 × 8 = 16 となるため、結果として (2, 8) を返します。

アルゴリズム：ハッシュを活用したアプローチ

この問題は、ハッシュテーブル（unordered_set）を利用することで効率的に解くことができます。手順は以下のとおりです。

1. 空のハッシュセットを用意します。
2. 連結リストを先頭から走査し、各ノードに対して次の処理を行います。
3. 現在の要素 current が K を割り切れるかどうかを確認します。
4. 割り切れる場合、商である K / current がすでにハッシュセットに登録済みかどうかを調べます。存在していれば、その2つの値が求めるペアです。
5. まだ存在しない場合は、current をハッシュセットに追加し、走査を続行します。

この手法では各要素を一度ずつ処理するだけで済むため、全要素同士を総当たりで比較する O(n²) の二重ループを回避でき、時間計算量は O(n) に抑えられます。

C++による実装例

#include <unordered_set>
#define MAX 100000
using namespace std;
class Node {
   public:
   int data;
   Node* next;
};
void append(struct Node** start, int key) {
   Node* new_node = new Node;
   new_node->data = key;
   new_node->next = (*start);
   (*start) = new_node;
}
bool isPairPresent(Node* start, int K) {
   unordered_set<int> s;
   Node* p = start;
   while (p != NULL) {
      int current = p->data;
      if ((K % current == 0) && (s.find(K / current) != s.end())) {
         cout << current << " " << K / current;
         return true;
      }
      s.insert(p->data);
      p = p->next;
   }
   return false;
}
int main() {
   Node* start = NULL;
   int arr[] = {2, 4, 8, 12, 15};
   int n = sizeof(arr)/sizeof(arr[0]);
   for(int i = 0; i<n; i++){
      append(&start, arr[i]);
   }
   if (isPairPresent(start, 16) == false)
   cout << "NO PAIR EXIST";
}

実行結果

2 8

出力より、2 × 8 = 16 を満たすペア (2, 8) が正しく検出されていることがわかります。なお、条件を満たすペアが連結リスト内に存在しない場合は "NO PAIR EXIST" と表示されます。

注意点

リストに 0 が含まれる場合、K % current の計算でゼロ除算が発生するため、実際の運用では 0 のチェックを事前に行うことが推奨されます。また、負の数や大きな値を扱う際も剰余演算の挙動に留意してください。