Find all the pairs in a given ordered set of numbers whose sum is equal to a given input sum

Loops Posted Sep 02, 2020

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:

1. declare pointers low = 0, high = length (numbers) -1
2. loop till low < high
3. find the sum of numbers at low and high
4. if the produced sum is less than expected, means that the sum should be on the higher side - so move the low towards right
5. if the produced sum is higher than expected, means that the sum should be on the lesser side - so move the high towards left
6. if the produced sum is equal to the expected, add this pair (low, high) to our output pairs and move the low and high indexes

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