6. Find all positive numbers in the array that have their opposites in it as well

6. At toptal.com : Algorithm : A numeric array of length N is given. We need to design a function that finds all positive numbers in the array that have their opposites in it as well. Describe approaches for solving optimal worst case and optimal average case performance, respectively. Use C. Question, Explanation, Solution.

Solution:

Note:

Three approaches will be addressed in this article: approach for O(N²) time, approach for O(N log₂ N) time, and approach for O(N) time. Only the approach for O(N.log₂N) time will be described in detail.

Also not that absolute value means the value without sign, which is just the positive value.

O(N²) Solution

With this solution, for each positive number, it is verified (compared) if any other number in the array is the opposite. The number of opposite pairs gives the answer. This solution has O(N²) time complexity. Any good computer programmer can code this solution, so it will not be addressed any further, in this article.

O(N.log₂N) Solution

Consider the example list:

-7, 4, -3, 2, 2, -8, -2, 3, 3, 7, -2, 3, -2 

By inspection, though inspecting is rather time consuming, the answer is [2, 2, 3, 7]. The subset (-2, -2, 2, 2) produces 2 pairs; the subset (-3 3) produces 1 pair; and the subset (-7 7) produces the last pair, making 4 pairs altogether. The set (-2, -2, 2, 2) has the pairs (-2, 2) and (-2, 2) which is same pair occurring twice.

Need for Special Custom Sorting
The special custom sorting is as follows:

If the numbers are not equal or opposite, they are sorted by their absolute value; but if they are (else), they are sorted by their sign. This leads to the following special custom sort (arrangement):

-2, -2, -2, 2, 2, -3, 3, 3, 4, -7, 7, -8 

The 4 pairs required can be seen or inferred.

This is not ordinary sort ascending or ordinary sort descending. A compare function is needed for this special custom sorting. The sort function will use the compare function. The code for this compare function is given along with the principal code below.

Principal Code
There is an issue with this problem and its solution at toptal.com/algorithms/interview-questions. At toptal.com/algorithms/interview-questions, the answer is [2 3 7 ] instead of [2, 2, 3, 7] . This means that the problem actually requires unique positive numbers and not just positive numbers with opposites. The principal code below produces unique positive numbers.

Complete Program

The complete program is (read the comments as well):

 #include <stdio.h> #include <stdlib.h> //for abs() and qsort() functions //compare function int compareFn(const void *a, const void *b) { int int_a = *((int *)a); int int_b = *((int *)b); if (int_a != int_b && int_a != -int_b) return abs(int_a) > abs(int_b); //from stdlib.h library else return int_a > int_b; } //principal code void find_numbers_with_opposites(int A[], int N) { qsort(A, N, sizeof(int), compareFn); //from stdlib.h library for (int i=1; i<N; i++) { if (A[i] > 0 && A[i - 1] == -A[i]) printf("%i ", A[i]); } } int main(int argc, char **argv) { int A[] = {-7, 4, -3, 2, 2, -8, -2, 3, 3, 7, -2, 3, -2}; int N = sizeof(A) / sizeof(A[0]); //no. of elements in A find_numbers_with_opposites(A, N); printf("\n"); return 0; } 

This implementation has an optimal average case runtime complexity of O(N.log₂N), with the sorting algorithm being the bottleneck.

O(N) Solution

This solution needs a hash function. The C language does not have a hash function. The C++ language has a hash function. So only the pseudo code using a hash function is provided below, so that anyone who has studied C++ can implement it. The pseudo code is:

FUNCTION find_numbers_with_opposites(numbers) table = HashTable<number, number> answer = List FOR number IN numbers IF number == 0 CONTINUE END IF key = abs(number) IF key not in table table[key] = number ELSE IF table[key] = -number answer.push(key) table[key] = 0 END IF END FOR 

Thanks for reading.