So I've been trying to complete this challenge and the challenge goes as follows:

Find the total number of pairs of indices(i, j) where Ai == Aj and i /= j.

Here is an example:

1 1 2

This array of size 3 has two pairs because indices 0,1 and 1,0 fit the condition given above.

Note: they don't say to assume that the array is sorted so I don't assume that.

Here is my strategy:

1.)

First sort the array with merge sort to achieve a time complexity of nlogn. The reason for this is to make searching for pairs easier.

2.)

Then we use binary search in a for loop which will give us a time complexity of nlogn + n. Let me explain this part more in depth.

The first part is nlogn because binary search is logn but we are going through the array N times. The n in the second part is something I'm not sure about but let me try to explain how I came about it.

3.)

Once we locate the target using binary search, we pass in the array, the arraysize, the target and the middle index where we found the target as arguments to the function countSherlockPairs. In this function, we have two individual for loops that goes from middle - 1 to 0 and middle + 1 to arraysize. In those for loops, we simply try to find other instances of the target. At the end of the function, we use this formula to find the total number of sherlock pairs.

return numOfSherlockPairs * (numOfSherlockPairs - 1) // n * (n-1)

So for example, if the array is 1 1 1, this formula will return 6. Verify this yourself to convince yourself that this is right.

I've already test my code and it works for some test cases but not for all test cases. I've tried to figure what possible test cases could be causing my algorithm to fail but I could not think of ones that could.

Here is my code:

Code:#include <stdio.h> #include <stdlib.h> int findSherLockPairs(); void mergeSort(int *, int, int); void mergeArray(int *, int, int, int); int binarySearch(int *, int, int); int countSherlockPairs(int *, int, int, int); int main() { int numOfTestCases, index, numOfSherLockPairs; scanf("%d", &numOfTestCases); for(index = 0; index < numOfTestCases; index++) { numOfSherLockPairs = findSherLockPairs(); printf("%d\n", numOfSherLockPairs); } return 0; } int findSherLockPairs() { int sizeOfArray, index; scanf("%d", &sizeOfArray); int *arr = malloc(sizeof(int) * sizeOfArray); for(index = 0; index < sizeOfArray; index++) { scanf("%d", &arr[index]); } mergeSort(arr, 0, sizeOfArray - 1); int numberOfSherlockPairs = 0, prevNumber = -1; for(index = 0; index < sizeOfArray; index++) { if(prevNumber != arr[index]) { numberOfSherlockPairs += binarySearch(arr, sizeOfArray, arr[index]); prevNumber = arr[index]; } } free(arr); return numberOfSherlockPairs; } void mergeSort(int *arr, int low, int high) { if(low < high) { int middle = (high + low) / 2; mergeSort(arr, low, middle); mergeSort(arr, middle + 1, high); mergeArray(arr, low, middle, high); } } void mergeArray(int *arr, int low, int middle, int high) { int *mergedArray = malloc(sizeof(int) * (high - low + 1)); int leftSide = low, rightSide = middle + 1, mergedIndex = 0; while(leftSide <= middle && rightSide <= high) { if(arr[leftSide] <= arr[rightSide]) { mergedArray[mergedIndex++] = arr[leftSide++]; } else mergedArray[mergedIndex++] = arr[rightSide++]; } while(leftSide <= middle) { mergedArray[mergedIndex++] = arr[leftSide++]; } while(rightSide <= high) { mergedArray[mergedIndex++] = arr[rightSide++]; } while(mergedIndex > 0) { arr[low + mergedIndex - 1] = mergedArray[mergedIndex - 1]; mergedIndex--; } free(mergedArray); } int binarySearch(int *arr, int sizeOfArray, int target) { int low = 0; int high = sizeOfArray - 1; int middle; int numOfSherlockPairs = 0; while(low <= high) { middle = (low + high) / 2; if(arr[middle] == target) { numOfSherlockPairs = countSherlockPairs(arr, sizeOfArray, target, middle); break; } else if(arr[middle] < target) { low = middle + 1; } else high = middle - 1; } return numOfSherlockPairs; } int countSherlockPairs(int *arr, int sizeOfArray, int target, int middle) { int numOfSherlockPairs = 1, index; for(index = middle - 1; index >= 0; index--) { if(arr[index] == target) { numOfSherlockPairs++; } else break; } for(index = middle + 1; index < sizeOfArray; index++) { if(arr[index] == target) { numOfSherlockPairs++; } else break; } return numOfSherlockPairs * (numOfSherlockPairs - 1); }