Expectation

In this problem, we will be given an unordered set of numbers and a number, we need to print all the pairs available in the set whose sum is equal to the given number. For example, if we are given a set of numbers [1, 2, 4, 8, 11, 9, 23, 5, 5, 6] and the sum is 10 - the output should be 8,2 9,1 5,5 6,4 since these are the only "pairs" of numbers which produce the given sum 10 among the numbers in the set.

Logic

This problem can be approached in different ways, such as like having nested loops which loop through each and every number of the set and perform a combination of sums and compare with the sum supplied. But we don't want to use this, as it takes higher time complexity because of the nested loops.

Instead, we can address this problem in this way: we can take a single number from the array and see if we had already seen the other part of the sum for this current number which forms the expected sum. For example, if we pick up the number 2 from the array, if we know that we had already seen an 8 in the array (because 10-2 = 8) then we can say that 2,8 form a pair for the solution.

To keep a memory of the past numbers we have already seen, we can maintain a set of the "complements" for this given number. So for the above example, as soon as we pick up 2 and realize that 8 is needed for this to be called a pair, we place the 8 inside this "complements" set and on further looping we can check if the current number is already there in the "complements" set or not. If the current number from the array is 8 and now since 8 is already there in the "complements" set, we can say that there was a 2 that has come before and 2,8 is a pair from the solution.

Logic:

The solution is approached as below:

1. loop through the given array of numbers
2. maintain a set of complement numbers
3. check if the expectedSum - currentNumber exists
4. if the number exists, add the currentNumber, expectedSum - currentNumber as a pair to resultPairs
5. if the number doesn't exist, add the expectedSum - currentNumber into the set

Code in C#:

        public void DoFindPairsForSum(int[] arrayOfNumbers, int expectedSum)
        {
            List<KeyValuePair<int, int>> expectedSumPairs 
              = new List<KeyValuePair<int, int>>();
            
            HashSet<int> complementSum = new HashSet<int>();

            for (int i = 0; i < arrayOfNumbers.Length; i++)
            {
                int complement = expectedSum - arrayOfNumbers[i];
                if (complementSum.Contains(arrayOfNumbers[i]))
                {
                    expectedSumPairs.Add(
                    new KeyValuePair<int, int>(arrayOfNumbers[i], complement));
                }
                else
                {
                    complementSum.Add(complement);
                }
            }

            foreach (var item in expectedSumPairs)
            {
                Console.WriteLine($"{item.Key},{item.Value}");
            }
        }

Note:

• Observe that we've taken a HashSet to place our complements instead of a List. Because HashSet offers a faster read access than a List.
• We're using List<KeyValuePair<int,int>> instead of a Dictionary<int,int> although Dictionary<int,int> is internally a list of KeyValuePair. This is because having a List<KeyValuePair<int,int>> keeps things simple and faster than a Dictionary.

*This problem is based on the question used in Google Example Coding Interview Video