# Count pairs in list of integers such that their addition is equal to the input value

Given a List<int>, the problem I am trying to solve is: Find the number of unique pairs in List<int> such that their addition is exactly equal to the input value.

The bottleneck is a nested for() loop that I have used to go through the list

// *** OPTIMIZE THIS LOOP ***
for (int i = 0; i < intList.Count - 1; i++)
{
for (int j = i + 1; j < intList.Count; j++)
{
if ((intList[i] + intList[j] == totalValue) &&
IsPairUnique(intList[i], intList[j]) == true)
{
nCombinations++;
}
}
}


How can this be made better for performance? I understand 'better' is a subjective word and has no real meaning as such. For a List<int> of size 50000 the code takes about 18 seconds on one of my VM. For 500000 it's way too worst. So, here by 'better' I mean 'faster'. Clearly this problem deserves much less than 18 seconds to solve in my opinion. With 1 Parallel.For() I have managed to get the loop time to 10-11 seconds, but I have a feeling that this whole algorithm needs a fresh set of eyes to look at.

Parallel.For(0, intList.Count - 1,
i =>
{
for (int j = i + 1; j < intList.Count; j++)
{
if ((intList[i] + intList[j] == totalValue) && IsPairUnique(intList[i], intList[j]) == true)
{
nCombinations++;
}
}
});


How can I speed this up? Full code from my console application is as below:

class TestClass
{
static List<int> compareList = new List<int>();
// GetPossibleCombination method.
// This method finds out the unique number of possible combinations where
// addition of any 2 values from the list is exactly equal to 'totalValue'
static int GetPossibleCombinations(List<int> intList, long totalValue)
{
// handle edge conditions
if (intList == null ||
intList.Count == 0 ||
intList.Count > 500000 ||
totalValue > 5000000000)
return 0;

compareList.Clear();
int nCombinations = 0;

// *** OPTIMIZE THIS LOOP ***
for (int i = 0; i < intList.Count - 1; i++)
{
for (int j = i + 1; j < intList.Count; j++) // start from this element onwards
{
if ((intList[i] + intList[j] == totalValue) && IsPairUnique(intList[i], intList[j]) == true)
{
nCombinations++;
}
}
}

return nCombinations;
}

// This method creates a list of possible values we have
static bool IsPairUnique(int v1, int v2)
{
if (compareList.Contains(v1 * 10 + v2) == true || compareList.Contains(v2 * 10 + v1) == true)
return false;
else
{
// else add a new one
}

return true;
}

static void Main(string[] args)
{
int intListSize = 50000; // Optimize it for numbers upto 500,000
long totalValue = 5000;

List<int> intList = new List<int>();
Random r = new Random();

for (int i = 0; i < intListSize; i++)
{
intList.Add(r.Next(0, 10000)); // populate random values.
}

Stopwatch sw = new Stopwatch();
sw.Start();

// Find the number of unique pairs in 'intList' such that
// their addition is exactly equal to 'totalValue'
int res = GetPossibleCombinations(intList, totalValue);

sw.Stop();
Console.WriteLine(sw.Elapsed.ToString());
}
}

• Does "unique pairs" mean "unique indexes", "unique values", or "unique combinations of values"? For example: if the data is 1, 1, 1 and the input value is 2, do we have zero, one or three unique pairs? – Oh My Goodness Feb 4 at 1:13
• @OhMyGoodness, "unique pairs" mean "unique combinations of values" from the list. e.g.: If 'totalValue' we are looking for is 5 and the value at list[i] is 2, list[i+1] is 3 and list[j] 3, list[j+1] is 2 then only one pair (either i, i+1 or j, j+1) should be considered. Hope this helps. – silverspoon Feb 4 at 1:55

The solution has a quadratic time complexity. If it solves the 50000-strong list in 18 seconds, I'd expect about 1800 seconds (aka 30 minutes) for a 500000 one. Notice that the problem is aggravated by the way you are looking for duplicates (and IsPairUnique doesn't look correct; it is prone to false positives).
• You could very well keep track of how many entries with a value of totalValue/2 you have (if totalValue is even) - if you have 2+ entries, count it as an additional pair. For all other numbers, it doesn't matter how many of them you've seen. – mabako Feb 4 at 12:51