We’re rewarding the question askers & reputations are being recalculated! Read more.

 3 deleted 24 characters in body edited Aug 6 '13 at 11:19 Juho 17.7k55 gold badges4545 silver badges9292 bronze badges I will assume the input arrayLet $$A$$ is alreadybe the sorted input array. Then, keepKeep two pointers $$l$$ and $$r$$ that go through the elements in $$A$$. The pointer $$l$$ will go through the "left part" of $$S$$$$A$$, that is the negative integers. The pointer $$r$$ does the same for the "right part", the positive integers. Below, I will outline a pseudocode solution and assume that $$0 \notin A$$ for minor simplicity. Omitted are also the checks for the cases where there are only positive or only negative integers in $$A$$. COUNT-PAIRS(A[1..N]): l = index of the last negative integer in A r = index of the first positive integer in A count = 0; while(l >= 0 and r <= N) if(A[l] + A[r] == 0) ++count; ++right; --left; continue; if(A[r] > -1 * A[l]) --left; else ++right;  It is obvious the algorithm takes $$O(N)$$ time. I will assume the input array $$A$$ is already sorted. Then, keep two pointers $$l$$ and $$r$$ that go through the elements in $$A$$. The pointer $$l$$ will go through the "left part" of $$S$$, that is the negative integers. The pointer $$r$$ does the same for the "right part", the positive integers. Below, I will outline a pseudocode solution and assume that $$0 \notin A$$ for minor simplicity. Omitted are also the checks for the cases where there are only positive or only negative integers in $$A$$. COUNT-PAIRS(A[1..N]): l = index of the last negative integer in A r = index of the first positive integer in A count = 0; while(l >= 0 and r <= N) if(A[l] + A[r] == 0) ++count; ++right; --left; continue; if(A[r] > -1 * A[l]) --left; else ++right;  It is obvious the algorithm takes $$O(N)$$ time. Let $$A$$ be the sorted input array. Keep two pointers $$l$$ and $$r$$ that go through the elements in $$A$$. The pointer $$l$$ will go through the "left part" of $$A$$, that is the negative integers. The pointer $$r$$ does the same for the "right part", the positive integers. Below, I will outline a pseudocode solution and assume that $$0 \notin A$$ for minor simplicity. Omitted are also the checks for the cases where there are only positive or only negative integers in $$A$$. COUNT-PAIRS(A[1..N]): l = index of the last negative integer in A r = index of the first positive integer in A count = 0; while(l >= 0 and r <= N) if(A[l] + A[r] == 0) ++count; ++right; --left; continue; if(A[r] > -1 * A[l]) --left; else ++right;  It is obvious the algorithm takes $$O(N)$$ time. 2 added 26 characters in body edited Aug 3 '13 at 15:44 Juho 17.7k55 gold badges4545 silver badges9292 bronze badges I will assume the input array $$A$$ is already sorted. Then, keep two pointers $$l$$ and $$r$$ that go through the elements in $$A$$. The pointer $$l$$ will go through the "left part" of $$S$$, that is the negative integers. The pointer $$r$$ does the same for the "right part", the positive integers. Below, I will outline a pseudocode solution and assume that $$0 \notin A$$ for minor simplicity. Omitted are also the checks for the cases where there are only positive or only negative integers in $$A$$. COUNT-PAIRS(A[1..N]): l = index of the last negative integer in A r = index of the first positive integer in A count = 0; while(l >= 0 and r <= N) if(A[l] + A[r] == 0) ++count; ++right; --left; continue; if(A[r] > -1 * A[l]) --left; else ++right;  It is obvious the algorithm takes $$O(N)$$ time. I will assume the input array $$A$$ is already sorted. Then, keep two pointers $$l$$ and $$r$$ that go through the elements in $$A$$. The pointer $$l$$ will go through the "left part" of $$S$$, that is the negative integers. The pointer $$r$$ does the same for the "right part", the positive integers. Below, I will outline a pseudocode solution and assume that $$0 \notin A$$ for minor simplicity. Omitted are also the checks for the cases where there are only positive or only negative integers in $$A$$. COUNT-PAIRS(A[1..N]): l = index of the last negative integer in A r = index of the first positive integer in A count = 0; while(l >= 0 and r <= N) if(A[l] + A[r] == 0) ++count; ++right; --left; continue; if(A[r] > -1 * A[l]) --left; else ++right;  It is obvious the algorithm takes $$O(N)$$ time. I will assume the input array $$A$$ is already sorted. Then, keep two pointers $$l$$ and $$r$$ that go through the elements in $$A$$. The pointer $$l$$ will go through the "left part" of $$S$$, that is the negative integers. The pointer $$r$$ does the same for the "right part", the positive integers. Below, I will outline a pseudocode solution and assume that $$0 \notin A$$ for minor simplicity. Omitted are also the checks for the cases where there are only positive or only negative integers in $$A$$. COUNT-PAIRS(A[1..N]): l = index of the last negative integer in A r = index of the first positive integer in A count = 0; while(l >= 0 and r <= N) if(A[l] + A[r] == 0) ++count; ++right; --left; continue; if(A[r] > -1 * A[l]) --left; else ++right;  It is obvious the algorithm takes $$O(N)$$ time. 1 answered Aug 3 '13 at 11:44 Juho 17.7k55 gold badges4545 silver badges9292 bronze badges I will assume the input array $$A$$ is already sorted. Then, keep two pointers $$l$$ and $$r$$ that go through the elements in $$A$$. The pointer $$l$$ will go through the "left part" of $$S$$, that is the negative integers. The pointer $$r$$ does the same for the "right part", the positive integers. Below, I will outline a pseudocode solution and assume that $$0 \notin A$$ for minor simplicity. Omitted are also the checks for the cases where there are only positive or only negative integers in $$A$$. COUNT-PAIRS(A[1..N]): l = index of the last negative integer in A r = index of the first positive integer in A count = 0; while(l >= 0 and r <= N) if(A[l] + A[r] == 0) ++count; ++right; --left; continue; if(A[r] > -1 * A[l]) --left; else ++right;  It is obvious the algorithm takes $$O(N)$$ time.