C++で積がk未満となるソート済み配列のペア数を効率よく数える方法

問題の概要

整数型の要素からなるソート済み配列と整数 k が与えられたとき、配列から作れるすべてのペアについて積を計算し、その積が k 未満となるペアの個数を求めるのが課題です。

入力例

int arr[] = {2, 7, 1, 0, 8}, int k = 10

出力例

Count of pairs in a sorted array whose product is less than k are: 7

解説

作成できるペアは次のとおりです。(2, 7) = 14(k以上)、(2, 1) = 2(k未満)、(2, 0) = 0(k未満)、(2, 8) = 16(k以上)、(7, 1) = 7(k未満)、(7, 0) = 0(k未満)、(7, 8) = 56(k以上)、(1, 0) = 0(k未満)、(1, 8) = 8(k未満)、(0, 8) = 0(k未満)。したがって、積が k 未満となるペアの個数は 7 となります。

入力例

int arr[] = {2, 4, 6, 8}, int k = 10

出力例

Count of pairs in a sorted array whose product is less than k are: 1

解説

作成できるペアは次のとおりです。(2, 4) = 8(k未満)、(2, 6) = 12(k以上)、(2, 8) = 16(k以上)、(4, 6) = 24(k以上)、(4, 8) = 32(k以上)、(6, 8) = 48(k以上)。したがって、積が k 未満となるペアの個数は 1 となります。

素朴なアプローチ（全探索）

この問題には複数の解き方があります。まずは最も直感的な素朴なアプローチ（ナイーブ法）から見ていきましょう。考え方はシンプルで、すべてのペアを実際に生成して積を確認する方法です。

• 整数型の配列を入力として受け取り、配列のサイズを計算して関数に渡します。

• k 未満の積を持つペアの個数を格納する一時変数 count を宣言します。

• i を 0 から配列サイズまで動かす外側の FOR ループを開始します。

• そのループの中で、j を i + 1 から配列サイズまで動かす内側の FOR ループを開始します。

• ループ内で product = arr[i] * arr[j] を計算し、product < k であれば count を 1 増やします。

• count を返します。

• 結果を出力します。

効率的なアプローチ（双方向ポインタ法）

次に紹介するのは、双方向ポインタ（Two Pointer）を使った効率的な手法です。配列がソート済みであることを利用することで、計算量を大幅に削減できます。

• 整数型の配列を入力として受け取り、配列のサイズを計算して関数に渡します。

• 条件を満たすペアの個数を格納する一時変数 count を宣言します。

• 左端ポインタ arr_0 を 0、右端ポインタ arr_1 を size - 1 に設定します。

• arr_0 が arr_1 より小さい間、ループを続けます。

• ループ内で arr[arr_0] * arr[arr_1] < k であれば、count に (arr_1 - arr_0) を加算して arr_0 を 1 増やします。そうでなければ arr_1 を 1 減らします。

• count を返します。

• 結果を出力します。

ここで「count += (arr_1 - arr_0)」の意味を補足しておきます。配列が昇順にソートされている場合、最小側の要素 arr[arr_0] と最大側の要素 arr[arr_1] の積が k 未満であれば、その間にあるどの要素との組み合わせでも積は必ず k 未満になります。つまり、一度の判定で (arr_1 - arr_0) 個のペアをまとめて数えられるため、全体の計算量は O(n²) から O(n log n)（ソート込み）または O(n)（既にソート済みの場合）に改善されます。

コード例（素朴なアプローチ）

#include <iostream>
using namespace std;
int pair_product(int arr[], int size, int k){
    int count = 0;
    int product = 1;
    for(int i = 0 ; i<size ; i++){
        for(int j = i+1; j<size; j++){
            product = arr[i] * arr[j];
            if(product < k){
                count++;
            }
        }
    }
    return count;
}
int main(){
    int arr[] = {5, 8, 2, 1, 3};
    int size = sizeof(arr) / sizeof(arr[0]);
    int k = 10;
    cout<<"Count of pairs in a sorted array whose product is less than k are: "<<pair_product(arr, size, k);
    return 0;
}

出力

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

Count of pairs in a sorted array whose product is less than k are: 5

コード例（効率的なアプローチ）

#include <iostream>
using namespace std;
int pair_product(int arr[], int size, int k){
    int arr_0 = 0;
    int arr_1 = size-1;
    int count = 0;
    int product = 1;
    while(arr_0 < arr_1){
        product = arr[arr_0] * arr[arr_1];
        if (product < k){
            count = count + (arr_1 - arr_0);
            arr_0++;
        }
        else{
            arr_1--;
        }
    }
    return count;
}
int main(){
    int arr[] = {1, 3, 4, 2, 1};
    int size = sizeof(arr) / sizeof(arr[0]);
    int k = 5;
    cout<<"Count of pairs in a sorted array whose product is less than k are: "<<pair_product(arr, size, k);
    return 0;
}

出力

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

Count of pairs in a sorted array whose product is less than k are: 10

まとめ

本記事では、ソート済み配列から選んだペアの積が k 未満となる組み合わせの数を求める問題を扱いました。二重ループによる全探索は実装が簡単ですが O(n²) の計算量が必要です。一方、双方向ポインタ法を使えば、ソート済みという前提を活かして各要素を一度ずつしか見ないため、大規模なデータに対しても高速に処理できます。用途に応じて両者を使い分けるとよいでしょう。