(Solution) Sales By Match / Sock Merchant – HackerRank Warm-up

Question

In this question, we are given an array of integers, where each number represents a particular colour of socks. We need to count how many pairs of socks are present, such that two socks of the same colour form a pair.

It is also mentioned that the highest number of distinct colours in the given array is 100.

Explanation

Let us take the following example:-

Suppose, the input is {1,2,5,1,1,5}
Where, 1=Green, 2=Purple, and 5=Yellow.

Thus, we have:

As we know, a pair consists of two same coloured socks. Thus, to find the number of pairs of a particular colour of socks, we can simply divide the number of socks of that colour by 2.

Thus on counting, we find that:

We have 3 green socks, 1 purple sock and 2 yellow socks.

Now we perform integer division to find the number of pairs of socks of each colour.

No. of pairs of green socks= 3/2=1.
No. of pairs of purple socks=1/2=0.
No. of pairs of yellow socks=2/2=1.

Thus, the final answer would be 1+0+1=2.

Solution

We will count the number of each sock of each colour using a frequency array, in O(n) time complexity.

We declare a frequency array of size 101. Thus, it will have indices starting from 0 to 100, which is exactly what we want, as the maximum number of distinct colours is 100.

Now we traverse the array using a linear for-loop. For every element, we increment the value of that index of the frequency array, which is the same value as the integer value representing the colour. This operation also takes O(n) time.

So, the total time complexity of this solution is O(n).

Thus in the above example {1,2,5,1,1,5}, the for-loop operations can be visualised as:

Array Element	Operation On Frequency Array (f)
1	f(1)=f(1)+1=0+1=1
2	f(2)=f(2)+1=0+1=1
5	f(5)=f(5)+1=0+1=1
1	f(1)=f(1)+1=1+1=2
1	f(1)=f(1)+1=2+1=3
5	f(5)=f(5)+1=1+1=2

After the for-loop has run, we get the updated frequency array as:

f(0)=0
f(1)=3
f(2)=1
f(3)=0
f(4)=0
f(5)=2
….(All the remaning elements are 0).

Now, divide the frequency of each colour of sock by 2 and add the results to a variable ‘c’.

At the start, c=0.

Array Element	Value of ‘c’
f(0)=0	c = c+f(0)/2 = 0+0/2 = 0+0 = 0
f(1)=3	c = c+f(1)/2 = 0+3/2 = 0+1 = 1
f(2)=1	c = c+f(2)/2 = 1+1/2 = 1+0 = 1
f(3)=0	c = c+f(3)/2 = 1+0/2 = 1+0 = 1
f(4)=0	c = c+f(4)/2 = 1+0/2 = 1+0 = 1
f(5)=2	c = c+f(5)/2 = 1+2/2 = 1+1 = 2

Thus, the total number of pairs of socks is stored in c (=2).

So, we finally return c.

Code Solution

Here’s the code solution for the approach mentioned above. Only the code snippet of the function has been provided below, that you can paste in HackerRank editor below the // Complete the sockMerchant function below. comment.

The solution has been provided in Java, C++ and C.

Sales By Match / Sock Merchant: Java Code Solution

static int sockMerchant(int n, int[] ar) {

/**
* f is the frequency array
* i is the control variable of for loops
* c stores the total number of pairs
*/

        int f[]=new int[101],i;
        int c=0;

//filling up the frequency array

        for(i=0;i<n;i++)
            f[ar[i]]++;

//counting the total number of pairs

        for(i=1;i<=100;i++)
            c+=f[i]/2;

        return c;
    }

Sales By Match / Sock Merchant: C++ Code Solution

int sockMerchant(int n, vector<int> ar) {

        /**
         * f is the frequency array
         * i is the control variable of for loops
         * c stores the total number of pairs
         */

        int f[101],i;
        int c=0;

        //initializing the array with all 0s

        for(i=0;i<101;i++)
            f[i]=0;

        //filling up the frequency array

        for(i=0;i<n;i++)
            f[ar.at(i)]++;

        //counting the total number of pairs

        for(i=1;i<=100;i++)
            c+=f[i]/2;

        return c;

    }

Sales By Match / Sock Merchant: C Code Solution

int sockMerchant(int n, int ar_count, int* ar) {
 
       /**
         * f is the frequency array
         * i is the control variable of for loops
         * c stores the total number of pairs
         */

        int f[101],i;
        int c=0;

        //initializing the array with all 0s

        for(i=0;i<101;i++)
            f[i]=0;

        //filling up the frequency array

        for(i=0;i<n;i++)
            f[ar[i]]++;

        //counting the total number of pairs

        for(i=1;i<=100;i++)
            c+=f[i]/2;

        return c;

}

Result

I hope I was able to explain the problem and the solution to you.

If you have any doubts regarding this problem or solution, feel free to comment down below. I will surely help you out.

If this article has helped you, it would be great if you consider sharing it with your friends.

See you in the next solution, Have a nice day!

FAQ