Find all pair of Array of Integers whose sum is equal to a given number in C#

It’s been a long time since I was trying to solve this problem. Whenever I tried I couldn’t solve it. I always miss some boundary conditions or something else. But today finally I solved it and it’s funny because approach is quite simple and I was trying code like building time machine ūüėõ

Array : [2, 4, 3, 5, 6, -2, 4, 7, 8, 9]
Given sum : 7
pairs whose sum is equal to value : 7
(2, 5) , (4, 3) , (-2, 9)

Array : [0, 14, 0, 4, 7, 8, 3, 5, 7]
Sum : 11
pairs whose sum equals: 11
(7, 4) , (3, 8) , (7, 4)

Array : [10, 9, 5, 9, 0, 10, 2, 10, 1, 9]
Sum : 12
pairs whose sum equals 12
(2, 10)

There are two ways of doing this,

Method 1: Brute Force approach – use two nested loops and make a pair and compare sum of them with given number. Its time complexity would be O(n^2).

Method 2: In this method we loop over the array only once. For each item of array, subtract this item from given number and if array item doesn’t exist in our list then add it otherwise print this item and subtraction of array item and given number. Its time complexity would be O(n) as we loop over only once and comparison are also less.

Code in C#:

static void Main(string[] args)
{
    int[] arr = { 0, 14, 0, 4, 7, 11,8, 3, 5, 7 };
    int n = 11;
    PrintPairs(arr, n);
    Console.ReadKey();
}
 
private static void PrintPairs(int[] arr, int n)
{
    var arrayItemList = new List<int>();
    foreach (var item in arr)
    {
        int remainingvalue = n - item;
        if (arrayItemList.Contains(remainingvalue))
        {
            Console.WriteLine($"({ item},{remainingvalue})");
        }
        else
        {
            arrayItemList.Add(item);
        }
    }
}
Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s