N 502 - TwoSum Value

For any given Array A[N], its TwoSum Value with respect to a number K is denoted by the number of ordered pairs {i, j} such that A[i] + A[j] = K.
i and j must satisfy the following :
1 <= i <= N and 1 <= j <= N.
i may be equal to j at times.
You are given the Array A[N] and the number K.
Find and print the TwoSum value for the array.

Hint : You may want to use binary search algorithm for efficient implementation.
Hint2 : BinarySearch works only on sorted Arrays. So you may want to use library sort (qsort in C and sort in C++) function to sort the array first.

INPUT

The first line contains a number N(1 <= N <= 10^5), the size of array A[N].
The second line contains N space separated integers denoting the elements of the array A. (1 <= A[i] <= 10^9).
The third line contains one number K(1 <= K <= 10^9), with respect to which the TwoSum value of the array A is to be found.

OUTPUT

Output one number that is equal to the TwoSum value of the given input array A[N] with respect to K.

Sample Input 0

10
1 2 3 4 5 6 7 8 9 10
10

Sample Output 0

9

Solution :

#include <cmath>

#include <cstdio>

#include <vector>

#include <iostream>

#include <algorithm>

using namespace std;

int binarySearch(int arr[], int first, int last, int key);

int find_sumPair (int A[], int n, int K)

 {

   int count=0;

   for( int i = 0;i<n;i++ )

   { 

      int x = binarySearch( A, 0, n-1, K-A[i] );

      if ( x==1 ) 

      count ++;

   }

 return count;

 }

int binarySearch(int arr[], int first, int last, int key){  

   int mid = (first + last)/2;  

   while( first <= last ){  

      if ( arr[mid] < key ){  

        first = mid + 1;     

      }else if ( arr[mid] == key )

      {  

          return 1;

      }else{  

         last = mid - 1;  

      }  

      mid = (first + last)/2;  

   }  

   if ( first > last ){  

       return 0;

        }

         return -1;

 }  

int main() {

    /* Enter your code here. Read input from STDIN. Print output to STDOUT */   

    int a;

    cin>>a;

    int ar[a];

    for(int i=0;i<a;i++)

        cin>>ar[i];

    sort(ar, ar+a);

    int b;

    cin>>b;

    int count= find_sumPair (ar, a, b);

   

    cout<<count;

    return 0;

}