Count index pairs which satisfy the given condition in C++

We are given an array of permutation of first N natural numbers. The goal here is to find the index pairs of elements that satisfy the condition mentioned below −

If an array is Arr[], then i,j are indexes, count element pairs such that Arr[i]+Arr[j]=max(Arr[x]) such that i<=x<=j.

That is, the sum of Arr[i] and A[j] is equal to the maximum element occurring between these two segments.

Input

Arr[]= { 2,4,1,3,6,5 }

Output

Count of index pairs which satisfy the given condition:1

Explanation − The sum of pairs is given −

2+4=6, 6 is maximum but not between 2 and 4.

2+1=3, 3 is not in between 2 and 1 and maximum between them is 4.

2+3=5, 5 is not in between 2 and 3 and maximum between them is 4.

2+6=8, 8 is not in between 2 and 6 and maximum between them is 4.

Similarly

1+5=6, 6 is in between 1 and 5 and maximum between them is 6.

Out of all only 1 pair is present that satisfies the condition.

Input

Arr[]= { 1,2,5,4,3 }

Output

Count of index pairs which satisfy the given condition:2

Explanation − The sum of pairs is given −

1+5=6, 6 is maximum but not between 1 and 5.

1+4=5, 5 is in between 1 and 4 and the maximum between them is 5.

2+3=5, 5 is in between 2 and 3 and the maximum between them is 5.

1+3=4, 4 is in between 1 and 3 but the maximum between them is 5.

Out of all 2 pairs are present that satisfy the condition.

Approach used in the below program is as follows

• Integer array Arr[] stores the numbers and size its length.

• Function countPairs(int A[],int n) takes an array and its size n as input and returns the count of pairs which satisfy the above condition..

• Variable count is used to store the initial value 0 for such pairs.

• Initialize max1 with the first element and its index in maxindex as 0 to store the value and index of maximum value found so far.

• Start traversing the array using for loop.

• Inside nested for loop if given A[j]>=max1 then update max1 and its index with j.

• For each pair of A[i] and A[j] if sum is equal to max1 and index maxindex is in between i and j, then increment count as condition is satisfied.

• After the end both loops return the result present in count.

Example

 Live Demo

// CPP implementation of the approach #include<bits/stdc++.h> using namespace std; // Function to return the count of // required index pairs int countPairs(int A[], int n){    // To store the required count    int count = 0;    int i,j,k;    int max1=A[0];    int maxindex=0;    for ( i = 0; i<n-1; i++){       for(j=i+1;j<n;j++){          if(A[j]>=max1){              max1=A[j];             maxindex=j;       }       if(A[i]+A[j]==max1 && maxindex>=i && maxindex<=j)          count++;       }    }    // Return count of subsegments    return count; } int main(){    int Arr[] = {3, 4, 6, 1, 5, 2};    int size =6;    cout <<endl<<"Count of index pairs which satisfy the given condition:"    <<countPairs(Arr,size);    return 0; }

Output

Count of index pairs which satisfy the given condition: 1