Sock Merchant

Can you explain why you choose HashSet over ArrayList etc. Is it due to time Complexity or due to the fact that a set cant contain duplicate elements.?

Fun fact, HashSet.remove() returns true if it can remove, false otherwise. No need to check .contains() first

rocking solution :)

Since we know the color limit (100), you should probably use a boolean array rather than a hash-set. It will be much faster.

Awesome solution! Like was already alluded to, the if-statement can be simplified to

if (!colours.add(c[i])) {
    pairs++;
    colours.remove(c[i]);
}

This is because the "add" method of a hashset will return false if it tries to add a duplicate.

Thanks for SET !!

Your solution is really good.Thanx..

It's useless on such small n <= 100. You wasted your time just to look more "smart". Disliked.

How do you make the measure of Space Complexity?

In C++ this was accomplished faster using a vector.

-unordered_set<> (hashset) performs insertions in O(n) and removals in O(n), plus the O(n) algorithm

-set<> performs insertions in O(nlogn) and removals in O(1), plus algorithm O(n)

-Altering a vector element is done in O(1), plus algorithm for O(n) total

I timed these each to be sure; using vectors took 1/7th the time of set<>.

colors.remove(c[i]); why?

when I use arrraylist instead of hashset, i get array_bound_out of_exception. why?

static int sockMerchant(int n, int[] ar) {
        // Complete this function
        Arrays.sort(ar);
        int count=0;
        for(int i=0;i<n-1;i++){
            if(ar[i]==ar[i+1]){
                count=count+1;
                i=i+1;
            }
        }
        return count;
    }

time complexity O(nlogn) space complexity O(1)

I liked your implementation! Here is my spinoff version in C#. My version doesn't remove any keys. In case, you want to go back to the your map to get the total value.

int pair_count = 0;
Dictionary<int, int> socks = new Dictionary<int, int>();
int counter = 0;
foreach(int sock in ar){
    if(!socks.ContainsKey(sock)){
        socks.Add(sock, 1);
    } else {
        socks[sock]++;
        if(socks[sock] % 2 == 0){
            pair_count++;
        }
    }
}

I think it's the key, right? colors.remove(c[i]);

Well, I think it is much simpler:

Here is C# solution:

return a.GroupBy( x => x ).Select( x => (x.Count() - (x.Count() % 2)) / 2).Sum();

Your idea is good but time complexity is not O(n) If all the numbers are different time cimplexity will be O(n^2).

Very nice solution, and fun creative use of a hashtable :-D

Thanks for introducing me to Counters!

I used Counter too!

Alternatively, without an import:

input()
socks = input().strip().split()
pairs = 0

for element in set(socks):
	pairs += socks.count(element) // 2
print(pairs)

There's also no need for integer casting, since we're just counting like things; and these are really just labels, not numbers we'll be doing arithmetic on.

You can even save another line by doing a list comprehension:

from collections import Counter

input()
counter = Counter(input().strip().split(' '))
print(sum(i//2 for i in counter.values()))

My solution with just one line of code:

print sum([c.count(x)/2 for x in set(c)])

Nice! Still wondering though if my potential interviewer would feel cheated by me importing this Counter class... Definitely good for a HackerRank competition though :)

Even shorter version using Python functionals (map and lambda)

    from collections import Counter
    n = int(input())
    socks = Counter(input().split())
    print(sum(map(lambda x: x//2, socks.values())))

I used your code, but the compiler says 'Invalid Syntax'. Can you help me with it?

Thanks dude.I was thinking the same but your code helped me implement it..:)

Why you are doing it in O(nlogn),when it can be done in O(n)?

hehe, this is exactly as I did it (but I used javascript and named the variable t "socksTotal")

Nice

Bro, When i was using this type of algorithm i am getting extra elements into the array after sorting 0 10 10 10 10 20 20 20 30 50 4196598 0 1641141296 32766 0 0 0 0 1095651141 32512

thanks dude although iam not aware of languge that you used but i got logic....

I've done the same haha but without using Array class. Did bubble sort to sort the array.

Sir, why add that i++ inside the if block? I cannot understand how it effects the program. Please help.

This worked perfectly for me.

I wish,c++ has a sort function!!.

Came up with exactly the same solution.

static int sockMerchant(int n, int[] ar)
{
    Arrays.sort(ar);
    int pairs=0;
    for(int i=0;i<n-1;i++)
    {
        if(ar[i]==ar[i+1])
        {
            ++pairs;
            ++i;
        }
    }
    return pairs;
}

Really helpfull bro...TYSM..

I did the exact same thing lol

Isn't necesary to initilize the array with a for loop. The arrays are initilized using the default value of his data type, in this case the boolean raw type, which his default value is false.

You're making it little complex can be done with same approach in simple way.

adding 1 on input number indexes and divide count by ignoring < 1 values. But whole approach is same. Using a driver array. :)

Or simply:

while(n-->0){
    if(++f[in.nextInt()] % 2 == 0) count++; 
}

with f an array of size 101.

Buddy, I did the same, but with simply arrays. Not boolean. Could u pls tell me where I went wrong?

int main(){
    int n,i,flag[100]={0},count=0,sock;
    cin>>n;
    while(n--)
        {
        cin>>sock;
        flag[sock]++;
    }
    for(i=0;i<100;i++)
        {
        if((flag[i]%2==0) && flag[i]!=0)
            count++;
    }
    cout<<count;
    return 0;
}

The sorting itself would take O(n log n). I think the main purpose here is to solve within O(n), by using hashset or boolean array.. Imma noob, and I'm just suggesting here :)

excellent logic

Superb logic man!!! that c[j]=0 just reduced a whole lot of problems that occured.

Nice logic ,,, while yu use a[j]=0,its covert that element to zero,,

that c[j]=0 was a great idea mate

why are you printing count?we should print the no. of pairs?

How could it possibly run in O(1) when there's a graph search?

Pretty good solution. Thanks! Learnt another way we could use dictionaries

i'm beginner programmer. can you please tell me why you have taken n-1?

in place of short int, i put int and i am getting my output as '9'. please tell me where do i go wrong?

No need of filter here. My solution was:-

Console.WriteLine(c.GroupBy(x => x).Select(x => x.Count() / 2).Sum());