using System;
using System.Collections.Generic;
using System.Linq;
// Problem: take a collection of numbers where a matching pair equals a sum that is provided
// inputs: array: [1,2,3,4], sum: 8
// brute force approach is log(n^2)
class MainClass {
static void Main() {
Console.WriteLine(MatchingPairEqualsQuadratic(new int[] {1,2,3,9}, 8));
Console.WriteLine(MatchingPairEqualsQuadratic(new int[] {-5,-3,4,11}, 8));
Console.WriteLine(MatchingPairEqualsLinear(new int[] {1,2,3,9}, 8));
Console.WriteLine(MatchingPairEqualsLinear(new int[] {-5,-3,4,11}, 8));
}
static bool MatchingPairEqualsQuadratic(int[] arry, int sum) {
if (arry.Length == 1) return false;
for (int i=0; i < arry.Length; i++) {
for (int j=1; j < arry.Length; j++) {
if (arry[i] + arry[j] == sum) return true;
}
}
return false;
}
// assuming a sorted list of numbers
// the number starting at the beginning index is the smallest number and the number at the ending index is the largest number
// which defines the range. When summing the largest and smallest if the sum is smaller than the target number then move the index
// of the smaller number and of the sum is larger then move the index of the larger number
static bool MatchingPairEqualsLinear(int[] arry, int sum) {
if (arry.Length == 1) return false;
int startIndex = 0;
int endIndex = arry.Length - 1;
int currentSum = arry[startIndex] + arry[endIndex];
if (currentSum == sum) return true;
while ( currentSum != sum) {
if (currentSum < sum) {
startIndex++;
} else {
endIndex--;
}
if (startIndex >= endIndex) break;
currentSum = arry[startIndex] + arry[endIndex];
}
return currentSum == sum;
}
}
