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.
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:
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:
*This problem is based on the question used in Google Example Coding Interview Video
Loops • Added 5 months ago