Fill count of distinct pairs of integers form an array whose sum if a given number in C#

Input: a = [ 2, 4, 3, 5, 6, -2, 4, 7, 8, 9]

Number k = 7

Pair Count = (2, 5), (4, 3), (-2, 9) = 3

Constraints: In a pair numbers should be different and all the pairs should be unique.

Lets say, a = [6, 6, 3, 9, 3, 5, 1]

k = 12

Possible pairs: (6 , 6), (3, 9), (9, 3)

But as per given constraints,  (6, 6) is invalid. And, (3,9) and (9, 3) both are same so we’ll consider only one of them.

Algorithm:

Step1: Prepare a dictionary and add all the items of the array into this dictionary. Array items as KEY and their frequency as VALUE. As we don’t care about the value of this dictionary, we just need a better data structure, to get our item fast, and dictionary is best for such kind of tasks.

Step2: Now as all the unique items have  been inserted in dictionary, so loop over given array and check for (K – array item). If this exists as KEY in dictionary that means there is a pair and it would be (K – array item, array item). But, once we have found a pair we need to check it should not be the same item. If all the constraints are satisfied then increase the count of pairs.

Step3: Now after all these we have number of pairs. But is this our output? Nope.

In our dictionary we have all the unique items of the array, that means for a pair, it contains both the items into this dictionary. For example, items 3,4 both are in dictionary and in our count variable we included pair (3, 4) and (4, 3). But as per our constraints we need to include them only once. So in count of pairs would be our (count variable / 2).

C# Code:

        static void GetNumberOfPairs()
        {
            int[] a = { 2, 4, 3, 5, 6, -2, 4, 7, 8, 9 };
            int k = 7;
            int count = NumberOfPairs(a, k);
            Console.WriteLine(count);
        }
        static int NumberOfPairs(int[] a, long k)
        {
            var count = 0;
            var dict = new Dictionary<int, int>();
            foreach (int item in a)
            {
                if (dict.ContainsKey(item))
                {
                    dict[item]++;
                }
                else
                {
                    dict.Add(item, 1);
                }
            }

            for (int i = 0; i < a.Length; i++)
            {
                if (dict.ContainsKey((int)k - a[i]) && (k - a[i] != a[i]))
                {
                    count++;
                }
            }

            return count / 2;
        }
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