lukes712 '''
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)
oldDoctor 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 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 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.
Remyohajinwa this solution is good
4LPH4 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 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.
changhaoran144 Seems your code is not complete.
COD_TLS200005 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 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 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?
nischal8 [deleted]
oldDoctor [deleted]
blakefisch [deleted]xjzhang Fun fact, HashSet.remove() returns true if it can remove, false otherwise. No need to check .contains() first
itaravin rocking solution :)
cantonios 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 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 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
taieddie8 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.
hakkirizakucuk 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; }
surajgupta842682 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?
thelamehacker [deleted]
anonymouse_pal [deleted]
gpbuffo 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 Thanks for SET !!
abhi2rast Your solution is really good.Thanx..
coolash123 [deleted]
ScienceD It's useless on such small n <= 100. You wasted your time just to look more "smart". Disliked.
Johny4529 How do you make the measure of Space Complexity?
driftwood 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 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?
nive24071997 when I use arrraylist instead of hashset, i get array_bound_out of_exception. why?
saif01md 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)
rajatwason30 But sorting of an array itself has a time complexity of n^2. so how can the time complexity of your program be nlogn??
varun130196 Inbuilt sorting methods use best sorting methods with least time complexity. so it'll be o(n log n)
rajatwason30 Can you please provide the source code for the sorting you are talking about? Thanks in advance.
iam_ghanshyam Depends. Mostly randomized quicksort() which most probably takes O(nlogn) time complexity.
15bcs036 bilkul sahi h bhai
iam_ghanshyam In your code "ar[]" will take space complexity of O(n) right?
kshitijgarg59 [deleted]
alex_k_stamatis 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 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 Too long
return ar.GroupBy(a => a).Sum(a => a.Count() / 2);
kshitijgarg59 Can u pls elaborate the use of groupby and what is meant by a=>a
olshme 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 }}
kshitijgarg59 thanks for the explanation
mariojsanchez15 int pairs = 0; HashSet< Integer > socks = new HashSet< Integer >(); for( int sock : ar ) if( !socks.add( sock ) ) { pairs++; socks.remove( sock ); } return pairs;
rpareek347 [deleted]
HabiburRahman Your idea is good but time complexity is not O(n) If all the numbers are different time cimplexity will be O(n^2).
mortenrobinson Very nice solution, and fun creative use of a hashtable :-D
tjorgais0021 when we remove an element from hashset, does the size of hashset remain same?...if not, then i think the loop should be dynamic? plz explain?
BeastT23 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 Thanks for introducing me to Counters!
congge I used Counter too!
lukas5 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.
askarovdaulet [deleted]askarovdaulet 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)
lukas5 Unfortunately, you're right.
liuyushan 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 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.
krzysiuup [deleted]
pa1985 This one is really interesting:
pairs += socks.count(element) // 2
How does it work?
BeastT23 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... :)
fran_roldans My solution with just one line of code:
print sum([c.count(x)/2 for x in set(c)])
tadamori_yoshi for Python 3
print (sum(c.count(x)//2 for x in set(c)))
jae_duk_seo LOL this is really good
askarovdaulet [deleted]askarovdaulet 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).
askarovdaulet 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 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 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 [deleted]bL4ck_r4bb1t [deleted]
maxim_marquez I used your code, but the compiler says 'Invalid Syntax'. Can you help me with it?
BeastT23 Can you be more specific? Does it tell you what line because I just ran this and it works fine. Are you using python?
kiroshh95 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); } }
rahulsinghrlp5 Thanks dude.I was thinking the same but your code helped me implement it..:)
rajmalhotra91195 Why you are doing it in O(nlogn),when it can be done in O(n)?
tushar_thos [deleted]
ravichandrae But the solution takes O(1) space. This might work well in memory constrained environments.
topmangabank so what he sorted doesnt use space huh
Greydon hehe, this is exactly as I did it (but I used javascript and named the variable t "socksTotal")
dhirajhimani Nice
codedas_dyanesh 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
kiroshh95 This code i wrote when i had no knowledge abt time complexity and such things...so it would better ignore this...
Vipin_panwar thanks dude although iam not aware of languge that you used but i got logic....
Vipin_panwar [deleted]
saurabh_a_dhabe I've done the same haha but without using Array class. Did bubble sort to sort the array.
kalbatprog7 Sir, why add that i++ inside the if block? I cannot understand how it effects the program. Please help.
sri_agni 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.
aviralft9 This worked perfectly for me.
alihashir4799 I wish,c++ has a sort function!!.
topmangabank It has
codertoaster 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; }
U_C_Mokal Really helpfull bro...TYSM..
stevehan2001 I did the exact same thing lol
lewap_ruzam 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 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 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. :)
alexandre_ragal1 Or simply:
while(n-->0){ if(++f[in.nextInt()] % 2 == 0) count++; }
with f an array of size 101.
Unremarkable Not bad, but we can remove the if if we do:
while(n-- > 0) { pairs += socks[in.nextInt()]++ % 2; }
positivedeist_07 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 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; } }
fflayol You might replace for(i=0;i<=100;i++) with for(i=0;i<100;i++)
gaurav_ruhela07 remove flag[i]%2==2 from if condition. and also remove count++, instead put count+=flag[i]/2
kumar_vikash0894 [deleted]kumar_vikash0894 if(flag[i]!=0 || flag[i]!=1){ count = count+ flag[i]/2; }
singhtanvi460 if u will use % then count will not be incremented when a number occurs 5 times or odd any number of times and in 5 there will be 2 pairs so instead writing if statement just write count=count+flag[i]/2
kunaldeepreddy 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 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 :)
tushar2693 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 excellent logic
ayushsaxena92910 Superb logic man!!! that c[j]=0 just reduced a whole lot of problems that occured.
rospython Nice logic ,,, while yu use a[j]=0,its covert that element to zero,,
Nithinchowdary that c[j]=0 was a great idea mate
dabhishek910 why are you printing count?we should print the no. of pairs?
ipg_2016069 it atually print the pairs, run in IDE you will understand
protojas #!/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
pavel_yeremenko How could it possibly run in O(1) when there's a graph search?
protojas 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
pavel_yeremenko 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?
changhaoran144 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 [deleted]suyashg1 Pretty good solution. Thanks! Learnt another way we could use dictionaries
RodneyShag 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.
ScienceD 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 i'm beginner programmer. can you please tell me why you have taken n-1?
ScienceD 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!
Crystal_star in place of short int, i put int and i am getting my output as '9'. please tell me where do i go wrong?
Sort 765 Discussions, By:
Please Login in order to post a comment