In this problem, we will be given a sorted 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,5,6,7, 9,11,48,64, 84] and the sum is 8 - the output should be 1,7 2,6 since these are the only "pairs" of numbers which produce the given sum 8 among the numbers in the set.
This problem is similar to the other example Find all the pairs in a given unordered set of numbers whose sum is equal to a given input sum, except that in this case the given input is actually a sorted set instead of an unordered set.
Since we already know that the set is sorted in some order (ascending or descending), we can use our low-high approach we used in sorting the unordered set of binary numbers, where the low represents the starting indexes and high represents the ending indexes. As we move the low and high against each other we can find out which pair matches the given sum as we move.
Logic:
The approach goes as below:
Code in C#:
public void DoFindPairsForSumOrdered(
int[] arrayOfNumbers,
int expectedSum)
{
List<KeyValuePair<int, int>> expectedSumPairs
= new List<KeyValuePair<int, int>>();
int low = 0, high = arrayOfNumbers.Length - 1;
while (low < high)
{
int sum = arrayOfNumbers[low] + arrayOfNumbers[high];
if (sum == expectedSum)
{
expectedSumPairs.Add(
new KeyValuePair<int, int>(arrayOfNumbers[low], arrayOfNumbers[high]));
low++; high--;
}
else if (sum > expectedSum)
{
high--;
}
else if (sum < expectedSum)
{
low++;
}
}
foreach (var item in expectedSumPairs)
{
Console.WriteLine($"{item.Key},{item.Value}");
}
}
*This problem is based on the question used in Google Example Coding Interview Video
Loops • Added 5 months ago