Following is the abridged(simplified) problem statement for the above problem.
Given an array containing values in the range [-10,10], find out how many number of matching pairs are possible?
A pair of numbers is said to be matching if one value is negative of the other (two zeros are also considered matching pair).
Consider the following examples.
[-6, 0, 1, 6, 0, -1] contains 3 matching pairs. Indices are (0,3), (1,4), (2,5)
[0, 0, 0, -5 ,3, 5] contains 4 matching pairs. Indices are (0,1), (0,2), (1,2), (3,5)
Since the problem is to find the count of matching pairs, we can always iterate through each possible pair and get the required answer. But this solution has a time complexity of O(n2).
long long result = 0;
for( i = 0; i < n-1 ; i++ )
{
for( j = i+1; j < n; j++ )
{
if(input[i] == -input[j])
result++;
}
}
cout << result << endl;
Let us look at more efficient solution. Since the given values are in specific range, we can store the frequencies of each number in an array of 21 values ( the size of the range [-10,10] ).
Count(-10) will be stored at index 0
Count(-9) will be stored at index 1
…
Count(0) will be stored at index 10
…
Count(10) will be stored at index 20
Now, the number of matching pairs is the sum of Count(-x) * Count(x) for 1<=x<=10
The number of possible pairs for n zeros is n*(n-1)/2
Below is the implementation of this algorithm in C++.