Search⌘ K
Home/
Courses/
Algorithms for Coding Interviews in C#

Solution: Find Two Numbers That Add Up to n

Explore various approaches to solving the problem of finding two numbers that add up to n in detail.

We'll cover the following...

Solution 1: Brute force

C# 9.0
using System;
using System.Collections.Generic;
class Program
{
    /// <summary>
    /// Method to find two numbers that add up to n.
    /// </summary>
    /// <param name="arr">n array of integers.</param>
    /// <param name="n">The integer number n.</param>
    public static int[] FindSum(int[] arr, int n)
    {
        for (int i = 0; i < arr.Length; i++)
        {
            for (int j = 0; j < arr.Length; j++)
            {
                if (arr[i] + arr[j] == n && i != j)
                {
                    return new int[] { arr[i], arr[j] };
                }
            }
        }
        return new int[0];
    }
    public static void Main()
    {
        Console.WriteLine("[" + string.Join(", ", FindSum(new int[] { 1, 2, 3, 4 }, 5)) + "]");
    }
}

Explanation

This is the most time-intensive but intuitive solution. We traverse the whole list, and for each element in the list, check if any two elements add up to the given number n. So, we use a nested for loop and iterate over the entire list for each element.

Time complexity

Since we iterate over the entire list of nn elements, the time complexity is O(n2)O(n^2).

Solution 2: Sorting the list

C# 9.0
using System;
using System.Collections.Generic;
class Program
{
    static int BinarySearch(int[] arr, int item)
    {
        int first = 0;
        int last = arr.Length - 1;
        int found = -1;
        while (first <= last && found == -1)
        {
            int mid = (first + last) / 2;
            if (arr[mid] == item)
            {
                found = mid;
            }
            else
            {
                if (item < arr[mid])
                {
                    last = mid - 1;
                }
                else
                {
                    first = mid + 1;
                }
            }
        }
        return found;
    }
    /// <summary>
    /// Method to find two numbers that add up to n.
    /// </summary>
    /// <param name="arr">n array of integers.</param>
    /// <param name="n">The integer number n.</param>
    public static int[] FindSum(int[] arr, int n)
    {
        Array.Sort(arr);
        for (int i = 0; i < arr.Length; i++)
        {
            int index = BinarySearch(arr, n - arr[i]);
            if (index != -1 && index != i)
            {
                return new int[] { arr[i], arr[index] };
            }
        }
        return new int[0];
    }
    public static void Main()
    {
        Console.WriteLine("[" + string.Join(", ", FindSum(new int[] { 1, 2, 3, 4 }, 5)) + "]");
    }
}

Explanation

While solution 1 is very intuitive, it is not very time-efficient. A better way to solve this is by first sorting the list. Then, for each element in the list, we use a binary search to look for the difference between that element and the intended sum. We can implement the BinarySearch method however we like, recursively or iteratively. So, if the intended sum is nn and the first element of the sorted list is a0a_0 ...