使用 C++ 统计满足 arr[i] * arr[j] > arr[i] + arr[j] 的 (i, j) 对数

给定一个包含 n 个正数的数组。目标是统计满足 arr[i]*arr[j] > arr[i]+arr[j] 的有序对 (i,j) 的数量，其中 0<=i<j<n，n 为数组元素个数。

我们将使用两个 for 循环遍历数组以计算每一对数。现在计算 arr[i] 和 arr[j] 的乘积和和。如果乘积大于和，则计数器加一。

让我们通过示例来理解。

输入 − 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[]。

• 使用变量 n 存储 Arr[] 的长度。

• 函数 countPairs(int arr[], int n) 以数组及其长度作为输入，并打印乘积大于和的数对的数量。

• 使用两个 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]) //condition
            { 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

Sunidhi Bansal

更新于: 2020年8月29日

614 次浏览

开启你的职业生涯

完成课程获得认证

开始学习