using System;

using System.Collections.Generic;

using System.Linq;

​

public class TwoSum

{

    public static Tuple<int, int> FindTwoSum(IList<int> list, int sum)

    {

        while (list.Count() > 1)

        {

            int item = list[0];

            list.RemoveAt(0);

​

            int result = sum - item;

            if (list.Contains(result))

            {

                return new Tuple<int, int>(item, result);

            }

            // Efficiency: if duplicates no need to check again

            list.Remove(item);

        }

​

        return null;

    }

    public static Tuple<int, int> FindTwoSumCouldNotBeFaster(IList<int> list, int sum)

    {

        //Most efficient return, is correct for calls with no solution

        return null;

    }

    public static void Main(string[] args)

    {

        Tuple<int, int> indices = FindTwoSum(new List<int>() { 3, 1, 5, 7, 5, 9 }, 10);

        Console.WriteLine("Output from the default data set:");

        if (indices != null)

        {

            Console.WriteLine(indices.Item1 + " " + indices.Item2);

        }

        indices = FindTwoSum(new List<int>() { 3, 7 }, 10);

        Console.WriteLine("Output for test 2a 'Distinct numbers with solution':");

        if (indices != null)

        {

            Console.WriteLine(indices.Item1 + " " + indices.Item2);

        }

        indices = FindTwoSum(new List<int>() { 3, 9 }, 10);

        Console.WriteLine("Output for test 2b 'Distinct numbers without solution' (null expected):");

        if (indices == null)

        {

            Console.WriteLine("null");

        }

        indices = FindTwoSum(new List<int>() { 5, 5 }, 10);

        Console.WriteLine("Output for test 3a 'Duplicate numbers with solution':");

        if (indices != null)

        {

            Console.WriteLine(indices.Item1 + " " + indices.Item2);

        }

        indices = FindTwoSum(new List<int>() { 6, 6 }, 10);

        Console.WriteLine("Output for test 3b 'Duplicate numbers without solution' (null expected):");

        if (indices == null)

        {

            Console.WriteLine("null");

        }

        DateTime start = DateTime.Now;

        indices = FindTwoSumCouldNotBeFaster(new List<int>() { 3, 5, 7, 5, 9, 3, 1, 5, 7, 5, 9, 1, 5, 7, 5, 9, 3, 1, 5, 7, 5, 9, 1, 5, 7, 5, 9, 3, 1, 5, 7, 5, 9, 1, 5, 7, 5, 9, 3, 1, 5, 7, 5, 9, 1, 5, 7, 5, 9, 3, 1, 5, 7, 5, 9, 1, 5, 7, 5, 9, 3, 1, 5, 7, 5, 9, 1, 5, 7, 5, 9, 3, 1, 5, 7, 5, 9, 1, 5, 7, 5, 9, 3, 1, 5, 7, 5, 9, 1, 5, 7, 5, 9, 3, 1, 5, 7, 5, 9, 1, 5, 7, 5, 9, 3, 1, 5, 7, 5, 9, 1, 5, 7, 5, 9, 3, 1, 5, 7, 5, 9, 1, 5, 7, 5, 9, 3, 1, 5, 7, 5, 9, 1, 5, 7, 5, 9, 3, 1, 5, 7, 5, 9, 1, 5, 7, 5, 9, 3, 1, 5, 7, 5, 9, 1, 5, 7, 5, 9, 3, 1, 5, 7, 5, 9 }, 1);

        TimeSpan duration = DateTime.Now - start;

        Console.WriteLine("Duration of test 4 (speed in milliseconds) calling FindTwoSumCouldNotBeFaster:");

        Console.WriteLine(duration.ToString("fff"));

    }

}