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

Solution: Find Two Numbers That Add Up to n

Explore various approaches to find two numbers that add up to a given sum n using C#. Understand the brute force method, sorting with binary search, dictionary-based lookups, and HashSet usage, along with their time complexity to choose the optimal solution.

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 ...