A basket is full with \$n\$ colored balls. For each color except one, there are at least 2 balls with that color. Find the color which only has one ball. in \$O(n)\$ space complexity.
What if each ball is repeated exactly twice?
You can consider the input to be an array or a list or any container of colors as strings with a maximum length of 100
This is code-golf so the shortest code in bytes wins.
Solely as an expression:
min(B,key=B.count)
Full, standalone program with input and output, 34 chars:
B=input()
print min(B,key=B.count)
edit: What gnibbler said.
input instead of raw_input and () around the print. Since the input format isn't specified, why not assign single letter codes to each colour? eg "rrgbb", then you can drop the split(). And use min instead of sorted FTW
\$\endgroup\$
&1=#:'=" "\:0:0
Takes input from stdin as a space separated list
k)&1=#:'=" "\:0:0
red red green blue blue
"green"
&1=#:'=" "\:0:0 runs fine for 15.
\$\endgroup\$
{.(~./:#/.~);:1!:1[1
A lot prettier than the previous attempt. Takes input from keyboard.
Makes an assumption that wasn't necessary in the previous version - that there is exactly one colour with one ball. If there are 2 colours with one ball you'll get the first that appears in the list, if there are no colours with only one ball you'll get the colour with the least balls.
Example:
{.(~./:#/.~);:1!:1[1
green green red blue blue
┌───┐
│red│
└───┘
SELECT C FROM B GROUP BY C HAVING COUNT(C)=1
SELECT C FROM B GROUP BY C HAVING COUNT(C)>1
Using the same sort of format as Keith Randall's answer of a function that takes an array and returns the element/colour that only occurs once.
R=lambda B:[a for a in B if B.count(a)<2][0]
Alternatively, if I need to read in colours from the command line and output the colour that is unique (which takes 60 chars):
B=raw_input().split();print[a for a in B if B.count(a)<2][0]
<2 rather than ==1 to save a char.
\$\endgroup\$
O(1) is a subset of O(n).
\$\endgroup\$
Commented
Jul 11, 2012 at 3:00
#(some(fn[[c n]](if(= n 1)c))(frequencies%))
That's a lambda function. Example:
(#(some(fn[[c n]](if(= n 1)c))(frequencies%))
[:red :red :red :blue :green :blue :yellow :yellow])
=> :green
n contains the list.
Cases[Tally@n,{x_,1}:>x]
After a tremendous amount of help from w0lf, here's the source code.
' '/:x.&{x{1$=},,1=\;},
? is displayed if there is not one unique color. For the sake of keeping the number of characters down to a minimum, the question mark was used (this of course can be changed to something more meaningful).
' '/:x.&{x{1$=},,1=\;},'?'or
' '/:x # split up each element and assign it to 'x'
.& # copy the last element in the stack and do a "setwise and"
{x # start filtration process and invoke 'x'
{1$=} # checks for an equality comparison
,, # find the count of each unique character
1= # compare value to '1'
\; # leave only value that has count of '1' on the stack
}, # close filtration process and print element on stack
'?'or # OPTIONAL: is printed if no element with a count of '1' is found
.m
.m is a builtin function which return the least frequent element in a list.
If you are not allowed to use a builtin to solve the challenge, then
it's 4 2 bytes:
-2 thanks to @caird coinheringaahing
ʒ¢
from collections import*
R=lambda B:Counter(B).most_common()[-1][0]
which(table(x)==1)
B/⍨1=+/B∘.≡B←⎕
Takes input from the keyboard in the form of an APL list, so you need to put quotes around the colors 'like' 'this'. (Or use numbers.)
B/⍨1=+/B∘.≡B←⎕
⎕:
'green' 'green' 'red' 'blue' 'blue'
red
As a function (that takes a list, also 14 characters):
{⍵/⍨1=+/⍵∘.≡⍵}
it.min{a->it.count(a)}
Attribution and test case:
lone={it.min{a->it.count(a)}}
l = ['red','green', 'red', 'blue', 'green']
assert lone(l) == 'blue'
assert lone(l) != 'red'
