Given a sorted array and parameter k, find the counter of the sum of two numbers greater than or equal to k

Question

I tried to find all the pairs in the array with the sum equal to k, the solution of which is taking the time O (n * log (n)). Here is a snippet of code -

  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;

I find it difficult to find all pairs with an amount greater than or equal to k. All I could think of was an O (n ^ 2) solution. O (n ^ 2) can be a brute force method for finding all pairs by iterating over an array. Can someone help me find a better solution, O (n) or O (nlgn) maybe (if it exists)

Answer 1

O(n) " " " ". , ( ++, ), , x, , k-x.

, , . , , , ; . O(n).

( , )

vector<int> a; // the given array
int r = a.size() - 1; 
for (int l=0; l<a.size(); l++) {
    while ((r >= 0) && (a[r] >= k - a[l]))
        r--;
    // now r is the maximal position in a so that a[r] < k - a[l]
    // so all elements right to r form a needed pair with a[l]
    ans += a.size() - r - 1; // this is how many pairs we have starting at l
}

, , , - O(n log n) . a[l] r, a[r]<k-a[l] ( r, ).

Answer 2

, O (log n) O (nlog n) , :

• , k/2, , k/2. , p + s >= k, p >= k/2 s >= k/2. , . O (log n).
• , k/2 + , " " ( k/2), , p + s >= k, p = k/2- t s >= k/2 + t. k/2 ( ). , , .

, {1,3,5,8,11} k = 10, k/2 = 5 {5,7}, {8,11}, {8, 11}. l * (l - 1)/2, l = >= k/2. l = 3, count = 3 * 2/2 = 3.

3- 7 (5-2 = 3 5 + 2 = 7), {3, 8} {3, 11}. 1- 9 (5-4 = 1 5 + 4 = 9), {1, 11} .

, k/2 < , O (log n).

, .

Answer 3

@ - .

. left right.
, left - , left 0, right a[left]+a[right] >= k .
, total_count += (a.size - right + 1).
left , right () . , .

, , x, totla_count += choose(2, a.size - x).

Answer 4

• (n log n)
• (i = 1 - n)
  • [i] + curr_node >= k, match = indexof (curr_nod) e
  • else,
  • If curr_node = leaf node, add all nodes after [match] to the list of valid pairs using [i]

Step 2 also accepts O (n log n). The for loop executes n times. Inside the loop, we perform a binary search for each step node ie log n. Therefore, the overall complexity of the algorithm is O (n log n).

Answer 5

This should do the job:

void count(int A[], int n) //n being the number of terms in array
{ int i, j, k, count = 0;
  cin>>k;

  for(i = 0; i<n; i++)
   for(j = 0; j<n; j++)
     if(A[i] + A[j] >= k)
      count++ ;

  cout<<"There are "<<count<<" such numbers" ;
}