Given a sorted array and a parameter k, find the count of sum of two numbers greater than or equal to k in linear time

Question

I am trying to find all pairs in an array with sum equal to k. My current solution takes O(n*log(n)) time (code snippet below).Can anybody help me in finding a better solution, O(n) or O(lgn) may be (if it exists)

  map<int,int> mymap;
  map<int,int>::iterator it;

  cin>>n>>k;

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

    cin>>a;
    
    if( mymap.find(a) != mymap.end() )
        mymap[a]++;
    else    
        mymap[a] = 1;
        
   }

   for( it = mymap.begin() ; it != mymap.end() ; it++ ){
            
    int val = it->first;
    
    if( mymap.find(k-val) != mymap.end() ){
        
        cnt += min( it->second, mymap.find(k-val)->second );
        it->second = 0;
        
    }
    
 }
  cout<<cnt;

Answer 1

Another aproach which will take O(log n) in the best case and O(nlog n) in the worst one for positive numbers can be done in this way:

1. Find element in array that is equal to k/2 or if it doesn’t exist than finds the minimum greater then k/2. All combinations with this element and all greater elements will be interested for us because p + s >= k when p>= k/2 and s>=k/2. Array is sorted, so binary search with some modifications can be used. This step will take O(log n) time.
2. All elements which are less then k/2 + elements greater or equal to "mirror elements" (according to median k/2) will also be interested for us because p + s >= k when p=k/2-t and s>= k/2+t. Here we need to loop through elements less then k/2 and find their mirror elements (binary search). The loop should be stopped if mirror element is greater then the last array.

For instance we have array {1,3,5,8,11} and k = 10, so on the first step we will have k/2 = 5 and pairs {5,7}, {8,11}, {8, 11}. The count of these pairs will be calculated by formula l * (l - 1)/2 where l = count of elements >= k/2. In our case l = 3, so count = 3*2/2=3.

On the second step for 3 number a mirror element will be 7 (5-2=3 and 5+2=7), so pairs {3, 8} and {3, 11} will be interested. For 1 number mirror will be 9 (5-4=1 and 5+4=9), so {1, 11} is what we look for.

So, if k/2 < first array element this algorithm will be O(log n).

For negative the algorithm will be a little bit more complex but can be solved also with the same complexity.