# Sock Merchant

- LM
lukes712 + 23 comments '''

`Set<Integer> colors = new HashSet<>(); int pairs = 0; for (int i = 0; i < n; i++) { if (!colors.contains(c[i])) { colors.add(c[i]); } else { pairs++; colors.remove(c[i]); } } System.out.println(pairs);`

'''

- Time Complexity: O(n)
- Space Complexity: O(n)

- AB
oldDoctor + 2 comments 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.?

gromki + 1 comment It's both. The call to contains() on colors will be O(1) for a HashSet versus O(n) for a List, and you won't store duplicates. The listing above can be improved by using the output of remove instead of calling contains first. You can also add directly to the Set when reading from Stdin rather than storing values first and iterating through them.

edlaierii + 2 comments What do you mean "Add directly to Set from read"? Is that a certain language that does that? I use C# and as far as I know I have to do something with the whole line before I can set it aside. Even a LINQ statement splits and reads the until line into an object before it then does any conversions or manipulations.

- RO
Remyohajinwa + 0 comments this solution is good

4LPH4 + 0 comments c# code for read input -> string[] ar_temp = Console.ReadLine().Split(' '); int[] ar = Array.ConvertAll(ar_temp,Int32.Parse);

Java code for read input - > for(int ar_i = 0; ar_i < n; ar_i++){ ar[ar_i] = in.nextInt(); }

You may have got the logic now, why he mentioned "Add directly to Set from read" - merge two forloops into one, this will give better performance.

tagaew + 3 comments Hashset storing values by placing values into an array by an index calculated according to GetHashCode of the value.

Actually I had the same idea but simpler:

int[] pairsToSell = new int[n]; int countToSell = 0; foreach(int sock in socks) { var ind = sock % n; pairsToSell[ind] +=1; if (pairsToSell[ind] == 2) { countToSell++; pairsToSell[ind] = 0; } } Console.WriteLine(countToSell);

Since sock color is a positive integer number, there is no need to take hash code of it. Instead I just used sock%n to recognize appropriate index.

- HC
changhaoran144 + 0 comments Seems your code is not complete.

COD_TLS200005 + 2 comments Will your program work for inputs:

2 2 4

i. e.

n=2

socks = {2, 4}I have executed your program on pen and paper. I got 1 as output, but we all know output should be 0.

Correct me if I am wrong, because I haven't executed it on a Computer.

edlaierii + 1 comment Where do you figure 1 from computing. The code looks for an int in an array of ints and each time it finds it it would add to the linq count, after that number is figured it gets divided by 2, that is then put into the variable for an answer. So it finds 2 once divides by 2, which we know is .5 but casting to int becomes 0.

COD_TLS200005 + 0 comments Since he keeps count in an array pairsToSell and access / modify it by variable ind = sock%n. For both socks his ind will be 0 (2 % 2 and 4 % 2), and he ends up incrementing pairsToSell[0] two times. So, instead of two '1's he gets one '2' in pairsToSell[0] which is when devided by 2 gives 1 as Output. Isn't it?

- NP
nischal8 + 0 comments [deleted]

- AB
oldDoctor + 0 comments [deleted] blakefisch + 0 comments [deleted]- X
xjzhang + 0 comments Fun fact, HashSet.remove() returns true if it can remove, false otherwise. No need to check .contains() first

itaravin + 0 comments rocking solution :)

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

kuzjka + 3 comments Or a BitSet if you wanna save some more memory :)

BitSet bitSet = new BitSet(COLOR_SIZE); for (int i = 0; i < size; i++) { int color = scanner.nextInt(); if (bitSet.get(color)) pairs++; bitSet.flip(color); }

cantonios + 0 comments I wouldn't worry about the 100 bytes taken by a boolean array of size 100. Maybe if you were talking about millions of colors, but then it might actually be worth using a HashSet depending on the size of 'n' and how many unique colors you expect to see

- ET
taieddie8 + 0 comments I don't know what a bitset is but I think you had the same idea as me. I tried using two long long ints to represent 100 numbers but it didn't work like I expected.

- HR
hakkirizakucuk + 1 comment When you use the 'flip' function, won't you end up having many useless '0's that will consume the memory as it loops through them? I think it is a better idea to remove the colors as soon as you pair them.

// VARIABLES: int n; list<int> S; // List of sock colors int input; int pairs = 0; cin >> n; while(cin >> input){ if(find(S.begin(), S.end(), input) != S.end()){ pairs += 1; S.remove(input); S.remove(input); continue; } S.push_back(input); } cout << pairs; return 0; }

- S
surajgupta842682 + 0 comments int sockMerchant(int n, vector ar) {

int i,a[100],s=0; for(i=0;i<100;i++) a[i]=0; for(i=0;i

}

why this code is not passing test case 3?

anonymouse_pal + 0 comments [deleted]gpbuffo + 0 comments 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.

chintan_chintan1 + 0 comments Thanks for SET !!

abhi2rast + 0 comments Your solution is really good.Thanx..

- AS
coolash123 + 0 comments [deleted] ScienceD + 0 comments It's useless on such small n <= 100. You wasted your time just to look more "smart". Disliked.

- JD
Johny4529 + 0 comments How do you make the measure of Space Complexity?

driftwood + 1 comment *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<>.

iam_ghanshyam + 0 comments But isn't it that you'll need to search the entire vector for every insert and searching in a vector takes O(n) time which'll ultimately take O(n^2) time if I'm not wrong?

- GS
- NG
nive24071997 + 0 comments when I use arrraylist instead of hashset, i get array_bound_out of_exception. why?

saif01md + 4 comments 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)

- RW
rajatwason30 + 1 comment But sorting of an array itself has a time complexity of n^2. so how can the time complexity of your program be nlogn??

- RR
varun130196 + 1 comment Inbuilt sorting methods use best sorting methods with least time complexity. so it'll be o(n log n)

- RW
rajatwason30 + 1 comment Can you please provide the source code for the sorting you are talking about? Thanks in advance.

iam_ghanshyam + 0 comments Depends. Mostly randomized quicksort() which most probably takes O(nlogn) time complexity.

15bcs036 + 0 comments bilkul sahi h bhai

iam_ghanshyam + 0 comments In your code "ar[]" will take space complexity of O(n) right?

- KG
kshitijgarg59 + 0 comments [deleted]

alex_k_stamatis + 0 comments 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]);

jackrus + 1 comment 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();

olshme + 1 comment Too long

return ar.GroupBy(a => a).Sum(a => a.Count() / 2);

- KG
kshitijgarg59 + 1 comment Can u pls elaborate the use of groupby and what is meant by a=>a

olshme + 1 comment Let's take the sample input from the task:

9 10 20 20 10 10 30 50 10 20

The input will be parsed to an array of ints

`ar`

. GroupBy will group the array of ints by values (the construction a => a) and creates a group for each unique value. For this input, GroupBy creates 4 groups.{key: 10, values: { 10, 10, 10 ,10 }} {key: 20, values: { 20, 20, 20 }} {key: 30, values: { 30 }} {key: 50, values: { 50 }}

- KG
kshitijgarg59 + 0 comments thanks for the explanation

- MS
mariojsanchez15 + 0 comments int pairs = 0; HashSet< Integer > socks = new HashSet< Integer >(); for( int sock : ar ) if( !socks.add( sock ) ) { pairs++; socks.remove( sock ); } return pairs;

rpareek347 + 0 comments [deleted]HabiburRahman + 0 comments Your idea is good but time complexity is not O(n) If all the numbers are different time cimplexity will be O(n^2).

- MR
mortenrobinson + 0 comments Very nice solution, and fun creative use of a hashtable :-D

BeastT23 + 8 comments Fun with Python :)

from collections import Counter input() socks, pairs = Counter(map(int,input().strip().split())), 0 for s in socks: pairs += socks[s]//2 print(pairs)

thebopshoobop + 0 comments Thanks for introducing me to Counters!

congge + 0 comments I used Counter too!

- LF
lukas5 + 4 comments 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.

- DA
askarovdaulet + 0 comments [deleted] - DA
askarovdaulet + 2 comments Unfortunately, I think this is O(n^2). Not that it matters too much for a problem with 100 socks :)

The issue is that set(socks) is of size O(n) and list.count() method's runtime is O(n)

- LF
lukas5 + 0 comments Unfortunately, you're right.

- YL
liuyushan + 2 comments What is the time complexity if I write the code in this way:

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

It should be O(n), but the space complexity increases since we create a space for A? Am I correct? Thanks for any suggestions.

BeastT23 + 1 comment Just realized there was a bug in this code while using this as reference to reply to another question. Set only keeps 1 of everything so this isn't going to give you the right answer.

- LF
lukas5 + 0 comments While the method is O(n^2), it does work. The set provides a unique list of colors which are then used against the list to get counts. The only difference in liuyushan's code is that he assigns the set to a variable.

krzysiuup + 0 comments [deleted]pa1985 + 1 comment This one is really interesting:

pairs += socks.count(element) // 2

How does it work?

BeastT23 + 0 comments While in the loop, it continuously adds half the count of the element to the pairs since you need 2 for a pair. Only problem with it is that if this were more of a harder challenge is that count is linear, so if you keep on doing that for all possible elements it goes to O(n^2) which on some challenges will easily time out given the size of the test data set. Not sure that covers your question but yeah... :)

- FR
fran_roldans + 3 comments My solution with just one line of code:

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

- A
tadamori_yoshi + 1 comment for Python 3

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

- JD
jae_duk_seo + 0 comments LOL this is really good

- DA
askarovdaulet + 0 comments [deleted] - DA
askarovdaulet + 0 comments Very nice and concise. Unfortunately, I think the complexity is O(n^2), since set(c) size is O(n) and list.count() runtime is O(n).

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

BeastT23 + 0 comments Depends on the question and what the interviewer is hoping to get out of the question from you. Does he want you to solve the problem without the help of a Container like Counter to see how you think with bare minimal or are you given free range to display the extent of your Python knowledge? This is somewhat analogous to a C++ interview where the interviewer restricts you to bare minimal(built in data types, arrays and/or pointers, etc.) and asks you to solve it without the STL in order to gain an idea of your fundementals in basic C++. As opposed to a bigger problem like searching or sorting where the interviewer gives you free reign with the STL to see that you understand data structures, algorithms, and other features of C++. Asking for clarification never hurt any one. :) So, like most answers to the problems in CS/programming, the answer is: it depends. Sorry for long winded answer. I just thought it was a good interview question worth answering. :)

lonso + 2 comments 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())))

bL4ck_r4bb1t + 0 comments [deleted]bL4ck_r4bb1t + 0 comments [deleted]

- AA
maxim_marquez + 1 comment I used your code, but the compiler says 'Invalid Syntax'. Can you help me with it?

BeastT23 + 0 comments Can you be more specific? Does it tell you what line because I just ran this and it works fine. Are you using python?

- RK
kiroshh95 + 14 comments pure simple alg....

public class Solution { public static void main(String[] args) { Scanner in = new Scanner(System.in); int n = in.nextInt(); int c[] = new int[n]; for(int c_i=0; c_i < n; c_i++){ c[c_i] = in.nextInt(); } Arrays.sort(c); int t=0; for (int i=0;i<n-1;i++){ if(c[i]==c[i+1]){ t++; i++; } } System.out.println(t); } }

- RS
rahulsinghrlp5 + 0 comments Thanks dude.I was thinking the same but your code helped me implement it..:)

- VK
rajmalhotra91195 + 2 comments Why you are doing it in O(nlogn),when it can be done in O(n)?

- TS
tushar_thos + 0 comments [deleted] ravichandrae + 1 comment But the solution takes O(1) space. This might work well in memory constrained environments.

- MS
topmangabank + 0 comments so what he sorted doesnt use space huh

- T
Greydon + 0 comments hehe, this is exactly as I did it (but I used javascript and named the variable t "socksTotal")

dhirajhimani + 0 comments Nice

codedas_dyanesh + 1 comment 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

- RK
kiroshh95 + 0 comments This code i wrote when i had no knowledge abt time complexity and such things...so it would better ignore this...

- VP
Vipin_panwar + 0 comments thanks dude although iam not aware of languge that you used but i got logic....

- VP
Vipin_panwar + 0 comments [deleted] saurabh_a_dhabe + 0 comments I've done the same haha but without using Array class. Did bubble sort to sort the array.

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

- SA
sri_agni + 0 comments because if u dont do that it will count same element twice. Ex:- input array- 5 6 5 7 5 8 sorted array- 5 5 5 6 7 8 it will make two pairs of element a[0]and a[1] ,a[1]and a[2] thats why you have to skip the counted element.

- AS
aviralft9 + 0 comments This worked perfectly for me.

alihashir4799 + 1 comment I wish,c++ has a sort function!!.

- MS
topmangabank + 0 comments It has

codertoaster + 2 comments 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; }

- UM
U_C_Mokal + 0 comments Really helpfull bro...TYSM..

- S
stevehan2001 + 0 comments I did the exact same thing lol

- PM
lewap_ruzam + 4 comments No need to store or count the input numbers:

import java.io.*; import java.util.*; import java.text.*; import java.math.*; import java.util.regex.*; public class Solution { public static void main(String[] args) { Scanner in = new Scanner(System.in); int n = in.nextInt(); boolean array[] = new boolean[101]; // the values of c_i are [1;100] for (int i=0; i<=100; i++) { array[i] = false; } int count = 0; for (int i=0; i < n; i++) { int c = in.nextInt(); if (array[c]) { array[c] = false; count += 1; } else array[c] = true; } System.out.println(count); } }

vmiam + 0 comments 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.

vivekwisdom + 0 comments 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. :)

- A
alexandre_ragal1 + 1 comment Or simply:

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

with f an array of size 101.

- AH
Unremarkable + 0 comments Not bad, but we can remove the if if we do:

while(n-- > 0) { pairs += socks[in.nextInt()]++ % 2; }

positivedeist_07 + 3 comments 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; }

positivedeist_07 + 1 comment Oopsie daisie :D sorry for bothering. I found out where I went wrong. So the for loop is modified as follows

for(i=0;i<=100;i++) { if(flag[i]!=0) { w = flag[i]/2; count += w; } }

- FF
fflayol + 0 comments You might replace for(i=0;i<=100;i++) with for(i=0;i<100;i++)

gaurav_ruhela07 + 0 comments remove flag[i]%2==2 from if condition. and also remove count++, instead put count+=flag[i]/2

- VK
kumar_vikash0894 + 1 comment [deleted]- VK
kumar_vikash0894 + 0 comments if(flag[i]!=0 || flag[i]!=1){ count = count+ flag[i]/2; }

kunaldeepreddy + 1 comment simple and sweet!!!

import java.io.

*; import java.util.*; import java.text.*; import java.math.*; import java.util.regex.*;public class solution {

`public static void main(String[] args) { Scanner in = new Scanner(System.in); int n = in.nextInt(); int c[] = new int[n]; int count=0; for(int i=0; i < n; i++){ c[i] = in.nextInt(); } Arrays.sort(c); for(int i=0; i <n-1;){ if(c[i]==c[i+1]) { count++; i=i+2; } else i++; } System.out.println(count); }`

}

positivedeist_07 + 0 comments 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 :)

- T
tushar2693 + 5 comments int count = 0; for(int i=0; i<n; i++){ if(c[i]!=0){ for(int j=i+1; j<n; j++){ if(c[i]==c[j]){ count++; c[j]=0; break; } } } } printf("%d", count);

Solution in C.. O(N^2).. Can it be optimized in C?? Please help..

koushik1998 + 0 comments excellent logic

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

- MR
iiitunastudy + 0 comments Nice logic ,,, while yu use a[j]=0,its covert that element to zero,,

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

dabhishek910 + 1 comment why are you printing count?we should print the no. of pairs?

ipg_2016069 + 0 comments it atually print the pairs, run in IDE you will understand

- JH
protojas + 3 comments #!/bin/python import sys n = int(raw_input().strip()) c = map(int,raw_input().strip().split(' ')) tot = 0 d = {} for i in range(n): if c[i] in d: d.pop(c[i]) tot += 1 else: d[c[i]] = 1 print tot

Python 2 O(n) solution.. "in" and "pop" both run O(1) for dictionaries

- PY
pavel_yeremenko + 1 comment How could it possibly run in O(1) when there's a graph search?

- JH
protojas + 1 comment are you asking how pop() runs in O(1)? Im not totally sure but I imagine it has something to do with keys being hashed for fast access. if no collisions in hashing you just need to hash a key to find its location in the dictionary

- PY
pavel_yeremenko + 1 comment So how would this 'magic' hashing work? Don't you still need to find hashed value? Surely by hash which is much faster but how would it be O(1) in worst case?

- HC
changhaoran144 + 0 comments As i know, python dictionary is a key-value model, like "map" in other language. For each key, use a certain way to compute the address and directly get the value.

HuangZhenyang + 0 comments [deleted]- SG
suyashg1 + 0 comments Pretty good solution. Thanks! Learnt another way we could use dictionaries

ScienceD + 2 comments C++ using selection sort and simple pair counter!

#include <iostream> using namespace std; int main() { short int n, pairs = 0; cin >> n; short int sock[n]; for(int i = 0; i < n; ++i) cin >> sock[i]; for(int i = 0; i < n-1; ++i) { //selection sort for(int j = i+1; j < n; ++j) { if(sock[j] < sock[i]) { short int tmp = sock[j]; sock[j] = sock[i]; sock[i] = tmp; } } } for(int i = 0; i < n-1; ++i) //number of pairs if(sock[i] == sock[i+1]) pairs++, i++; cout << pairs << endl; return 0; }

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

ScienceD + 0 comments I'm a beginner programmer too =)

I used n-1 cos if I'd use n, I will read some undentified memory! Look at j. Its j = i+1, if i would be n, j would be n+1, but we don't have n+1 element! It would contain some trash data!

Also in pairs counter we count i and i+1 sock, so i must not equal to the total sock amount, or we wil again step into trash values of undentified memory!

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

ddan88 + 1 comment C# solution with a single Linq expression:

int res = c.GroupBy(x => x) .Where(y => y.Count() >= 2) .Select(z => z.Count() / 2).Sum(); Console.WriteLine(res);

singii05 + 0 comments No need of filter here. My solution was:-

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

rshaghoulian + 0 comments ### Java solution - passes 100% of test cases

From my HackerRank solutions.

Use a HashSet instead of a HashMap for simpler code.

import java.util.Scanner; import java.util.HashSet; public class Solution { public static void main(String[] args) { /* Read some input */ Scanner scan = new Scanner(System.in); int n = scan .nextInt(); /* Count pairs */ HashSet<Integer> set = new HashSet<>(); int pairs = 0; for (int i = 0; i < n; i++) { int cost = scan.nextInt(); if (set.contains(cost)) { set.remove(cost); pairs++; } else { set.add(cost); } } /* Print output */ scan.close(); System.out.println(pairs); } }

Let me know if you have any questions.

Sort 649 Discussions, By:

Please Login in order to post a comment