Finding the possible number of equal pairs in an array

Question

I got this test online last week. here is an example:

given this array:

{ 1 , 2 , 4 , 5 , 1 , 4 , 6 , 2 , 1 , 4 }

on condition that

index(x) < index (y)

find the number of possible pairs (x,y).

where x = y.

the answer would be:

count = 7 - (0,4), (0,8), (4,8), (1,7), (2,5), (2,9), (5,9)

Edit3: added picture to clarify the pairs are elements from the same array. the picture has the first 3 pairs.

the first solution I came up with which was obviously bad:

public static int solution(int[] A)
    {
        int count = 0;
        for (int i = 0; i < A.Length; i++)
        {
            for (int j = i + 1; j < A.Length; j++)
            {
                if (A[i] == A[j])
                    count++;
            }
        }
        return count;
    }

basically, just count the number of possible pairs in each loop.

then after a bit of struggle I managed to do this:

public static int solution(int[] A)
        {     
            int count = 0;
            var dict = new Dictionary<int, int>();
            for (int i = 0; i < A.Length; i++)
            {
                if (!dict.Any(x => x.Key == A[i]))
                    dict.Add(A[i], 1);
                else
                    dict[A[i]]++;
            }

            foreach (var item in dict)
            {
                count += Factorial(item.Value) / 2 * Factorial(item.Value - 2);
            }

            return count;
        }

1- count how many times the number is present.

2- calculate the possible pairs for each number which is given by this formula:

where n is the number of repetitions and r = 2 (pair, 2 items)

Factorial is just a simple implementation of the function.

I feel like there is a lot to improve on this. what do you think?

Edit: added the Factorial Function as requested:

public static int Factorial(int N)
        {
            return N == 0
                       ? 1
                       : Enumerable.Range(1, N).Aggregate((i, j) => i * j);
        }

Edit2: I tested both and got 20s for the first method and 500ms for the second improved method.

the 100000 was the limit set by the test details.

here is the code for the test:

int[] testArray = new int[100000];
Random x = new Random();
for (int i = 0; i < testArray.Length; i++)
{                
   testArray[i] = x.Next(1, 10);
}
Stopwatch sw = new Stopwatch();
sw.Start();
solution(testArray);
sw.Stop();

Edit4:

Well, it seems like I messed up!

calculating factorial for numbers bigger 19 in intger is not possible, out of range.

the worse is I didn't even have to calculate it.

in my formula since r is a constant I could simplify it to

n* (n -1) / 2

thus avoiding the entire thing.

Answer 1

Based on the calculation of the number of pairs -your assertion is correct. The whole calculation method could be simplified by:

    public static List<KeyValuePair<int,int>> solution(int[] A)
    {

        //n(n-1)/2 number of pairs by a given set
        return  A.GroupBy(x => x).ToList().
            Select(y => new KeyValuePair<int, int>((y.Count() * (y.Count() - 1)) / 2, y.Key)).ToList();
    }