Finding an integer sum in an array of 1 000 000

Question

Given a large list of integers (more than 1 000 000 values) find how many ways there are of selecting two of them that add up to 0.... Is the question

What I have done is create a positive random integer list:

Random pos = new Random();
int POSNO = pos.Next(1, 1000000);
lstPOS.Items.Add(POSNO);
lblPLus.Text = lstPOS.Items.Count.ToString();
POSCount++;

And created a negative list:

Random neg = new Random();
int NEGNO = neg.Next(100000, 1000000);
lstNEG.Items.Add("-" + NEGNO);
lblNegative.Text = lstNEG.Items.Count.ToString();
NegCount++;

To do the sum checking I am using:

foreach (var item in lstPOS.Items)
{
    int POSItem = Convert.ToInt32(item.ToString());
    foreach (var negItem in lstNEG.Items)
    {
        int NEGItem = Convert.ToInt32(negItem.ToString());
        int Total = POSItem - NEGItem;
        if (Total == 0)
        {
            lstADD.Items.Add(POSItem + "-" + NEGItem + "=" + Total);
            lblAddition.Text = lstADD.Items.Count.ToString();
        }
    }
}

I know this is not the fastest route. I have considered using an array. Do you have any suggestions?

Answer 1

Let's see; your array is something like this:

  int[] data = new int[] {
    6, -2, 3, 2, 0, 0, 5, 7, 0, -2
  };

you can add up to zero in two different ways:

1. a + (-a) // positive + negative
2. 0 + 0 // any two zeros

in the sample above there're five pairs:

  -2 + 2 (two pairs): [1] + [3] and [3] + [9]
   0 + 0 (three pairs): [4] + [5], [4] + [8] and [5] + [8]

So you have to track positive/negative pairs and zeros. The implementation

 Dictionary<int, int> positives = new Dictionary<int, int>();
 Dictionary<int, int> negatives = new Dictionary<int, int>(); 
 int zeros = 0;

 foreach(var item in data) {
   int v;

   if (item < 0) 
     if (negatives.TryGetValue(item, out v))     
       negatives[item] = negatives[item] + 1;
     else
       negatives[item] = 1;  
   else if (item > 0) 
     if (positives.TryGetValue(item, out v))     
       positives[item] = positives[item] + 1;
     else
       positives[item] = 1;  
   else
     zeros += 1;
 } 

 // zeros: binomal coefficent: (2, zeros)
 int result = zeros * (zeros - 1) / 2;

 // positive/negative pairs
 foreach (var p in positives) {
   int n;

   if (negatives.TryGetValue(-p.Key, out n)) 
     result += n * p.Value; 
 } 

 // Test (5)
 Console.Write(result); 

Note, that there's no sorting, and dictionaries (i.e. hash tables) are used for positives and negatives so the execution time will be linear, O(n); the dark side of the implementation is that two additional structures (i.e. additional memory) required. In your case (millions integers only - Megabytes) you have that memory.

Edit: terser, but less readable Linq solution:

  var dict = data
    .GroupBy(item => item)
    .ToDictionary(chunk => chunk.Key, chunk => chunk.Count());

  int result = dict.ContainsKey(0) ? dict[0] * (dict[0] - 1) / 2 : 0;

  result += dict
    .Sum(pair => pair.Key > 0 && dict.ContainsKey(-pair.Key) ? pair.Value * dict[-pair.Key] : 0);