Sock merchant Problem: i am trying to do this with a different approach

Question

I am trying to solve Sock Merchant problem from HackerRank .

John works at a clothing store. He has a large pile of socks that he must pair by color for sale. Given an array of integers representing the color of each sock, determine how many pairs of socks with matching colors there are.

For example, there are n=7 socks with colors ar= [1,2,1,2,1,3,2] . There is one pair of color 1 and one of color 2 . There are three odd socks left, one of each color. The number of pairs is 2 .

My Code :

class Sock
{
    public static void  main(String args[])
    {
        int n=10;
        int ar[] = new int[]{1,1,3,1,2,1,3,3,3,3};
        int count = 0,number=0;

        for(int i=0;i<n-1;i++)
        {
            for(int j=i+1;j<n;j++)
            {
                if(ar[i]==ar[j])
                {
                    count++;
                }
            }

             if(count%2==0)
                number++;

        }
        System.out.println("Pairs =  "+number);
    }
}

I am trying to do this problem with different approach . like: First ar[0]=1 frequency is 3 , count=3 include itself, then if count>1 and if count%2==0 then increment number++, so again if 1 come ar[2]=1 then again count 1's frequency from ar[2]=1. then we got 1's frequency 3,2,1 from ar[0] to ar[6] ,ar[2] to ar[6], ar[4] to ar[6] .

so we got 1's pair 1 time , '2's pair 1 time : total= 2 pairs.

Answer 1

This can be done in O(n) time complexity and O(n) space if you use a hashtable.

Hashtable would have Key = color of Socks, Value = total count of each color.

total_count = dict()
for i in range(len(arr)):
    if arr[i] in total_count:
        total_count[arr[i]] += 1

pairs = 0
for i in total_count:
    pairs += int(total_count[i] / 2)

print(pairs)

Iterate once over the array and store each occurrence of color in a hashtable. Then iterate over the hashtable to check if counts of each color are divisible by 2. That would give you your pairs.

I did this in python but hope you get the point.

Answer 2

In this case you can get away with a nested loop because HackerRank is only going to test your solution on arrays of length up to 100. But if you want to take a different approach, think about how you would solve this problem yourself, manually, if you had a drawer full of socks and you wanted to count how many pairs there were. I don't think you would take a sock, count how many socks of that colour are in the drawer, then take another sock and count again, and so on!

The natural solution is to take the socks one at a time, keep them in a separate space aside from the drawer, and when you take a sock that pairs with one that you've kept aside, pair them together and put them somewhere else. That solution can be modelled in Java by using a Set to store the unpaired socks, and a counter variable to count the number of pairs. Each time you take a new sock from the array, if the same colour is already in the set, remove the one from the set and pair them up (i.e. add one to the counter), otherwise put the new sock into the set.

public int countPairs(int[] socks) {
    Set<Integer> oddSocks = new HashSet<>();
    int pairs = 0;
    for(int sock : socks) {
        if(oddSocks.contains(sock)) {
            oddSocks.remove(sock);
            pairs++;
        } else {
            oddSocks.add(sock);
        }
    }
    return pairs;
}

Answer 3

Your basic idea is OK, though it took me a bit to understand it. If there’s an even number of socks in the same colour to the right of this sock. then I can count it as belonging to a pair (if an odd number, then it may be the other sock of a pair, so don’t count it again).

I think that there are two errors in your program:

1. You must reset count to 0 for each iteration of your outer loop; the value from the previous iteration is irrelevant.
2. Since you are not counting the current sock in, you need an odd count, not an even one, to call a pair.

So your program becomes:

    int ar[] = { 1, 1, 3, 1, 2, 1, 3, 3, 3, 3 };
    int numberOfPairs = 0;

    for (int i = 0; i < ar.length - 1; i++)
    {
        int countSocksToTheRight = 0;

        for (int j = i + 1; j < ar.length; j++)
        {
            if (ar[i] == ar[j])
            {
                countSocksToTheRight++;
            }
        }
        if (countSocksToTheRight % 2 != 0)
        {
            numberOfPairs++;
        }

    }
    System.out.println("Pairs =  " + numberOfPairs);

I have tried to think of better variable names. I haven’t done any thorough testing. As the program stands, it outputs:

Pairs = 4

Alternative: As a complete aside and not answering anything you asked about, but possibly interesting for other readers: If I were to write the program, I would use two stream operations. I’d first use a stream from the array and group by sock color and count socks in each group. Next I’d do a new stream from the values of the map, dividing each sock count by 2 and throw away any remainder (any unmatched sock) to get the number of pairs of that colour, finally adding all the pair counts.

Answer 4

var res = 0; ar.sort(function(a,b){ return a-b }); for(var i=0; i<ar.length; i++){ if(ar[i]===ar[i+1]){ res++ } } return Math.ceil(res/2)

Answer 5

Try this, you can easily understand it

x=[]
y=[]
ar.sort()
while len(ar)>1:
 if ar[0]==ar[1]:
  x.append(ar[:2])
  del ar[:2]
 else:
  del ar[0]

Answer 6

def sockMerchant(n, ar):
check_bucket = {}
for i in range(len(ar)):
    if ar.count(ar[i]) > 1:
        check_bucket[ar[i]] = ar.count(ar[i])
for key, value in check_bucket.items():
    if check_bucket[key] % 2 != 0:
        check_bucket[key] = check_bucket[key] - 1

values = check_bucket.values()
total = round(sum(values) / 2)
return total  

this is works absolutely fine

Answer 7

Boby Robert's answer inspired this simplified version:

def sockMerchant(n, ar):
    pairs = 0
    arset = set(ar)
    for i in arset:
        pairs += int(ar.count(i) / 2)
    
    return pairs

Sets are frequently useful in Python as duplicate entries are automatically discarded. Then we just use the .count() built-in to get the total count of each type of sock, divide by two, and store the whole number value result.