# Finding the possible number of equal pairs in an array

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.

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

• It appears that your question is missing the Y array as stated by the condition index(x) < index (y). That indicates to me that the size of x has to be less than the size of y. Can you post a link to the test and/or check/edit your question? Aug 24 '20 at 6:59
• the y is from the same array, also where could I post the code online? @AlexLeo Aug 24 '20 at 7:08
• In other words Y = X+ 1 ? or Y is all the other elements with index greater than X? Add a link to the test in your question. Aug 24 '20 at 7:12
• @AlexLeo I edited the question to add a clarification. Aug 24 '20 at 7:16

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