C++でarr[i]*arr[j] > arr[i]+arr[j]を満たすペア（i, j）の個数を数える方法

正の整数からなる長さnの配列が与えられます。この問題の目的は、arr[i]*arr[j] > arr[i]+arr[j] かつ 0≦i＜j＜n を満たす順序付きペア（i, j）の個数を数えることです。ここで、nは配列内の要素数を表します。

2つのforループを使って配列を走査し、各ペアについて調べていきます。それぞれのペアに対してarr[i]とarr[j]の和と積を計算し、積が和より大きければカウントを1つ増やします。

具体例で確認してみましょう。

入力 − Arr[]= { 1,1,2,3 } N=4

出力 − ペアの個数 − 1

説明 − 条件を満たす唯一のペアは（2,3）です。

2*3=6 ＞ 2+3=5

入力 − Arr[]= { 2,2,2 } N=3

出力 − ペアの個数 − 0

説明 − 2*2も2+2もどちらも4になるため、積が和より大きくなるペアは存在しません。

本プログラムで使用するアプローチ

• 正の整数で初期化された整数型配列arr[]を用意します。

• Arr[]の長さを格納する変数nを定義します。

• 関数countPairs(int arr[], int n)は、配列とその長さを引数として受け取り、積が和より大きくなるペアの個数を出力します。

• ペアを構成する各要素について、2つのforループを使って配列を走査します。

• 外側のループは0≦i＜n−1、内側のループはi＜j＜nの範囲で繰り返します。

• arr[i]*arr[j]＞arr[i]+arr[j]という条件を判定し、真であればカウントを増やします。

• すべてのループが終了した時点で、countには積が和より大きいペアの総数が格納されています。

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

コード例

#include <bits/stdc++.h>
#include <math.h>
using namespace std;
int countPairs(int arr[], int n){
    int count=0;
    int sum=0;
    for(int i=0;i<n-1;i++){
        for(int j=i+1;j<n;j++){
            if(arr[i]*arr[j]>arr[i]+arr[j]) //条件判定
                { count++; }
        }
    }
    return count;
}
int main(){
    int arr[] = { 1,2,3,2 };
    int len = sizeof(arr) / sizeof(int);
    cout<<"Count of number of pairs :"<<countPairs(arr, len);
    return 0;
}

出力

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

Count of number of pairs :2