Finding duplicate balls in a basket?

samairtimer 09/12/2017. 12 answers, 693 views
code-golf

Question

A basket is full n colored balls . Except one ball all the other colors are repeating. Find the one color that does not repeat,in O(n) space complexity.

What if each ball is repeated exactly twice?

you can consider it to be an array or a list or any container with a capacity of 100

5 Comments
6 Peter Taylor 07/09/2012
Unless you specify some kind of input and output format (or the flexibility of what you allow) people are going to make vastly different assumptions.
2 MrZander 07/09/2012
This question isn't suited for CodeGolf. You need to specify a winning criteria. Otherwise, try StackOverflow.com if you are needing help.
Prince John Wesley 07/10/2012
Do you want us to find the duplicate balls as the title suggests?
samairtimer 07/10/2012
@PrinceJohnWesley Yes thats the whole idea!!
Rohan Jhunjhunwala 07/08/2016
-1 no input format specified, no output format specified... How you output the repeated ball? Index? Is it one indexed or zero indexed?

12 Answers


daniero 07/11/2012.

Python - 17 chars

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.

2 comments
1 gnibbler 07/11/2012
Python3 would be a little shorter - use 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
daniero 07/11/2012
Thanks! Yeah, I guess a string is within the bounds of 'any container' :D The question doesn't even mention input, so I think it's legit with 2.x's input() and have the user wrap quotes around it too.

tmartin 07/12/2012.

K, 17 15

&1=#:'=" "\:0:0

Takes input from stdin as a space separated list

k)&1=#:'=" "\:0:0
red red green blue blue
"green"
5 comments
Gareth 07/11/2012
I think you've got me beat this time - it takes me 15 characters just to get the separate strings.
Gareth 07/11/2012
...or maybe not - I've got the input down to 8 which at least gives me a fighting chance... :-)
tmartin 07/11/2012
Given the way you successively golfed the last one I wouldn't be surprised to see you beat me again. My solution can't get any shorter, I think.
Gareth 07/11/2012
No, I think 20 is my limit here.
skeevey 07/12/2012
No need to wrap this in a function, &1=#:'=" "\:0:0 runs fine for 15.

Gareth 07/11/2012.

J, 31 24 20 characters

{.(~./:#/.~);: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│
└───┘

Tester101 07/12/2012.

SQL - 44

Find Unique Color

SELECT C FROM B GROUP BY C HAVING COUNT(C)=1

Find Duplicate Colors

SELECT C FROM B GROUP BY C HAVING COUNT(C)>1
1 comments
Rohan Jhunjhunwala 07/08/2016
The right tool for the job!

JPvdMerwe 04/13/2017.

Python 2.7, 44 chars

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]
4 comments
gnibbler 07/10/2012
This is O(1) space complexity - which is usually better than O(n), but technically isn't what the question asks for :)
2 grc 07/11/2012
I think you could use <2 rather than ==1 to save a char.
Keith Randall 07/11/2012
@gnibbler: O(1) is a subset of O(n).
JPvdMerwe 07/11/2012
@grc: Thanks, amended the solution.

Álvaro Cuesta 07/11/2012.

Clojure - 44

#(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

DavidC 09/02/2012.

Mathematica 23

n contains the list.

Cases[Tally@n,{x_,1}:>x]

Rob 04/13/2017.

GolfScript, 23

After a tremendous amount of help from w0lf, here's the source code.

' '/:x.&{x{1$=},,1=\;},

DEMO


28 characters with the error checking

? 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

DEMO


Commentary

' '/: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

Keith Randall 07/10/2012.

Python 2.7, 67 chars

from collections import*
R=lambda B:Counter(B).most_common()[-1][0]

flodel 09/12/2012.

R - 18 chars

which(table(x)==1)

marinus 09/14/2012.

APL (14)

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=+/⍵∘.≡⍵}

Will Lp 09/16/2012.

Groovy - 22 chars

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'

HighResolutionMusic.com - Download Hi-Res Songs

1 BLACKPINK

Kiss And Make Up flac

BLACKPINK. 2018. Writer: Soke;Kny Factory;Billboard;Chelcee Grimes;Teddy Park;Marc Vincent;Dua Lipa.
2 Martin Garrix

Waiting For Tomorrow flac

Martin Garrix. 2018. Writer: Pierce Fulton;Mike Shinoda;Martijn Garritsen;Brad Delson.
3 John Legend

Written In The Stars flac

John Legend. 2018. Writer: Kiana Brown;Santoy;Kevin White;Mike Woods;MZMC;The Heavy Group;Rice N' Peas.
4 Martin Garrix

Access flac

Martin Garrix. 2018. Writer: Martin Garrix.
5 Martin Garrix

Yottabyte flac

Martin Garrix. 2018. Writer: Martin Garrix.
6 Alan Walker

Diamond Heart flac

Alan Walker. 2018. Writer: Alan Walker;Sophia Somajo;Mood Melodies;James Njie;Thomas Troelsen;Kristoffer Haugan;Edvard Normann;Anders Froen;Gunnar Greve;Yann Bargain;Victor Verpillat;Fredrik Borch Olsen.
7 Cardi B

Taki Taki flac

Cardi B. 2018. Writer: Bava;Juan Vasquez;Vicente Saavedra;Jordan Thorpe;DJ Snake;Ozuna;Cardi B;Selena Gomez.
8 Bradley Cooper

Shallow flac

Bradley Cooper. 2018. Writer: Andrew Wyatt;Anthony Rossomando;Mark Ronson;Lady Gaga.
9 Post Malone

Sunflower flac

Post Malone. 2018. Writer: Louis Bell;Billy Walsh;Carter Lang;Swae Lee;Post Malone.
10 Dyro

Latency flac

Dyro. 2018. Writer: Martin Garrix;Dyro.
11 Lady Gaga

I'll Never Love Again flac

Lady Gaga. 2018. Writer: Benjamin Rice;Lady Gaga.
12 Rita Ora

Let You Love Me flac

Rita Ora. 2018. Writer: Rita Ora.
13 Zara Larsson

Ruin My Life flac

Zara Larsson. 2018. Writer: Delacey;Michael Pollack;Stefan Johnson;Jordan Johnson;Sermstyle;Jackson Foote.
14 Halsey

Without Me flac

Halsey. 2018. Writer: Halsey;Delacey;Louis Bell;Amy Allen;Justin Timberlake;Timbaland;Scott Storch.
15 ZAYN

Fingers flac

ZAYN. 2018. Writer: Zayn Malik;Alex Oriet;David Phelan.
16 Dewain Whitmore

Burn Out flac

Dewain Whitmore. 2018. Writer: Dewain Whitmore;Ilsey Juber;Emilio Behr;Martijn Garritsen.
17 Mako

Rise flac

Mako. 2018. Writer: Riot Music Team;Mako;Justin Tranter.
18 Bradley Cooper

Always Remember Us This Way flac

Bradley Cooper. 2018. Writer: Lady Gaga;Dave Cobb.
19 Blinders

Breach (Walk Alone) flac

Blinders. 2018. Writer: Dewain Whitmore;Ilsey Juber;Blinders;Martin Garrix.
20 Julia Michaels

There's No Way flac

Julia Michaels. 2018. Writer: Ian Kirkpatrick;Justin Tranter;Julia Michaels;Lauv.

Related questions

Hot questions

Language

Popular Tags