Finding Sherlock Pairs

[deathslice]

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:

#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);
}

[algorism]

Your code is overcomplicated. Consider simplifying it.

[deathslice]

Funny enough, I was refactoring my code because I realize that I did not have to do a binary search(if it's sorted, usually it is best to use binary search but it is not needed in this case) and it came out looking like yours but there is a problem with your code and your analysis.

1.) Your time complexity is not exactly nlogn + n(only on average). It's n^2 + n because the worst case for quick sort is n^2(When it comes to time complexity we have to look at the worst case). This is the reason why I chose merge sort even though the space complexity for my program is now n but the size is only 100,000 which is still pretty small in the grand scheme of things.

2.) Take for example 1 1 1 2 2. The output should be 8 but with yours it would output 6.

Here is how mine looks.

#include <stdio.h>
#include <stdlib.h>

int findSherLockPairs();
void mergeSort(int *, int, int);
void mergeArray(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]);
   }

   if(sizeOfArray > 1)
   {
      mergeSort(arr, 0, sizeOfArray - 1);
   }

   int totalSherlockPairs = 0, sherlockPairs = 1;

   for(index = 1; index < sizeOfArray; index++)
   {
        if(arr[index] == arr[index - 1])
        {
           sherlockPairs++;
        }
        else
        {
            totalSherlockPairs += (sherlockPairs * (sherlockPairs - 1));
            sherlockPairs = 1;
        }
   }

   if(sherlockPairs != 1)
   {
       totalSherlockPairs += (sherlockPairs * (sherlockPairs - 1));
   }

   free(arr);

   return totalSherlockPairs;
}


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);
}

[algorism]

If you don't appreciate it you don't appreciate it, what can I do?
Anyway, if you ran it with your input you would see that it gives 8.
Later.

[deathslice]

Regardless, my code is only passing 3 test case out of 16 which tells me that there is a general case that I am missing. My logic is pretty much sound but there is something very obvious that I'm missing in my code and I just don't know what it is.

[deathslice]

Algorism, you know it is not that I don't appreciate your input.
I've tested and it does return 6. Trace it yourself and you will see.

Just so I can prove to you that 1 1 1 2 2 returns 6 given your code.

the first iteration is true: cnt++
the second iteration is true: cnt++
The third is false and sum is 6
The fourth iteration is true: cnt++
For loop terminates and cnt is greater than 1 but we have not updated sum because we are done with the for loop. oops!

[deathslice]

I've notice in their constraint section that the size of array could be as high as 100000. Now assuming that every element in that array was the same, that would mean that the total number of pairs is 100000 * (100000 - 1). This is obviously not big enough for a long or an int. So I changed it to a long long and I'm still failing a lot of their test cases. I'm taking a break from this.

[deathslice]

I finally got it right. It occurred to me suddenly that I was printing a long long as a unsigned integer and so I needed to change the printf specifier to %llu. I also needed to change the variable sherlockPairs to a long long as well. Cheers guys.

[algorism]

I've tested and it does return 6.

You are a liar. I actually ran it with your input and it prints 8. You obviously never ran it. It also passes all of the babyrank tests (on submission). If you actually have a copy of my code then post it. Otherwise you are proven a liar.

I erased the code because you are a thoughtless little moron and don't deserve any help. I won't display the code here since you'll just accuse me of changing it. If a mod can resurrect the original post (of post #2) I would agree to that. If not, c'est la vie. But you can go to hell you lying little creep.