C++で合計がx未満となるソート済み配列内のペアを数える方法

問題概要

整数型の要素からなるソート済み配列と整数変数xが与えられます。配列から2つの要素を選んでペアを作り、その合計がx未満になるペアが全部でいくつ存在するかを求めるのが課題です。

例1

入力: int arr[] = {2, 7, 1, 0, 8}, int x = 8

出力: 合計がx未満となるペアの数: 4

説明: 配列から作成できるすべてのペアとその合計は以下の通りです。
(2, 7) = 9(xより大きい)、(2, 1) = 3(x未満)、(2, 0) = 2(x未満)、(2, 8) = 10(xより大きい)
(7, 1) = 8(xに等しい)、(7, 0) = 7(x未満)、(7, 8) = 15(xより大きい)
(1, 0) = 1(x未満)、(1, 8) = 9(xより大きい)、(0, 8) = 8(xに等しい)
したがって、合計がx未満となるペアは (2, 1)、(2, 0)、(7, 0)、(1, 0) の4つとなります。

例2

入力: int arr[] = {2, 4, 6, 8}, int x = 10

出力: 合計がx未満となるペアの数: 2

説明: 作成できるペアは (2, 4) = 6(x未満)、(2, 6) = 8(x未満)、(2, 8) = 10(xに等しい)、(4, 6) = 10(xに等しい)、(4, 8) = 12(xより大きい)、(6, 8) = 14(xより大きい)です。よって、合計がx未満となるペアは2つです。

解法アプローチ

この問題には複数の解き方があります。まずはシンプルな全探索(ナイーブ)アプローチから見ていきましょう。

ナイーブアプローチの手順

• 整数型の配列を入力として受け取り、配列のサイズを計算して関数に渡します。
• 合計がx未満となるペアの個数を格納する一時変数countを宣言します。
• iを0から配列のサイズまでループさせます。
• その内側で、jをi+1から配列のサイズまでさらにループさせます。
• ループ内でsum = arr[i] + arr[j]を計算し、sum < xであればcountを1増やします。
• countを返し、結果を出力します。

この方法はすべてのペアを調べるため、時間計算量はO(n²)になります。

効率的なアプローチ(二ポインタ法)

配列がすでにソートされているという性質を利用すると、二ポインタ法によって計算量をO(n)まで削減できます。

• 整数型の配列を入力として受け取り、配列のサイズを計算して関数に渡します。
• 合計がx未満となるペアの個数を格納する一時変数countを宣言します。
• 左ポインタarr_0を0、右ポインタarr_1をsize-1に設定します。
• arr_0 < arr_1の間ループを続けます。
• ループ内でarr[arr_0] + arr[arr_1] < xが成立すれば、配列がソート済みのため、arr_0とarr_1の間のすべての要素とのペアも条件を満たします。そこでcount += (arr_1 - arr_0)としてarr_0を1増やします。条件を満たさない場合はarr_1を1減らします。
• countを返し、結果を出力します。

コード例(ナイーブアプローチ)

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

出力

Count of pairs in a sorted array whose sum is less than x are: 4

コード例(効率的なアプローチ)

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

出力

Count of pairs in a sorted array whose sum is less than x are: 4

まとめ

ソート済み配列における「合計がx未満のペア」のカウント問題は、二重ループによる全探索でも解けますが、配列がソートされている性質を活かした二ポインタ法を使えば、時間計算量をO(n²)からO(n)へと大幅に改善できます。どちらの手法も空間計算量はO(1)であり、追加のメモリは不要です。