# 1-line Python O(N^2)

• Update:

1-line solution as suggested by @StefanPochmann

``````def numberOfBoomerangs(self, points):
return sum(
n * (n - 1)
for x1, y1 in points
for n in collections.Counter(
(x1 - x2) ** 2 + (y1 - y2) ** 2
for x2, y2 in points).values())
``````

Old:

Just for fun:

``````def numberOfBoomerangs(self, points):
dist = lambda (x1, y1, x2, y2): (x1 - x2) ** 2 + (y1 - y2) ** 2

return sum(
n * (n - 1)
for x1, y1 in points
for n in collections.Counter(dist((x1, y1, x2, y2)) for x2, y2 in points).values())
``````

Here is a more clear version:

``````def numberOfBoomrangs(self, points):
nums = 0
for x1, y1 in points:
distance = collections.defaultdict(int)
for x2, y2 in points:
dx = abs(x2 - x1)
dy = abs(y2 - y1)
d = dx * dx + dy * dy
distance[d] += 1

nums += sum(n * (n-1) for n in distance.values())
return nums
``````

• @voiceup one mistake line: dy = abs(y2 - x1)

• @tdd1000

Thank you for the catch! Just fixed it.

• Could make it a one-liner by ditching `dist`, it doesn't help much anyway. And no point using `abs` before squaring.

``````def numberOfBoomerangs(self, points):
return sum(
n * (n - 1)
for x0, y0 in points
for n in collections.Counter((x - x0)**2 + (y - y0)**2
for x, y in points).values())``````

• @StefanPochmann
Yeah you are right.

Initially I was thinking using something like `x * x + y * y` to achieve better performance than `x ** 2 + y ** 2`. Although they are virtually the same thing, I believe in the benchmark the first expression is considerably faster in Python. I don't know how I got so dumb and ended up writing the lambda expression in that way (`abs(x1 - x2) ** 2 + abs(y1 - y2) ** 2`)...

Another consideration is to make the second line shorter and arguably more readable.

In retrospection, I think I actually like your 1-line version, and will edit my post..

• @voiceup said in 1-line Python O(N^2):

I believe in the benchmark the first expression is considerably faster in Python

What benchmark? You mean submitting here? That varies a lot even with the exact same code. How much faster was it, in how many attempts?

I just tried this, where they look about the same:

``````>>> timeit(lambda: Counter(x*x for x in xrange(10000)), number=1000)
3.3120313425821735
>>> timeit(lambda: Counter(x**2 for x in xrange(10000)), number=1000)
3.3315958179443044
``````

Also, the stuff other than the multiplication is responsible for most of the time. And even the pure thing looks pretty much the same:

``````>>> timeit('x * x', 'x = 42', number=10**7)
0.35808611698361403
>>> timeit('x**2', 'x = 42', number=10**7)
0.3640849920255249
``````

• @StefanPochmann

Interesting, here is what I got:

``````# Python 2.7.12
>>> timeit('x * x', 'x = 42', number=10**7)
0.4510629177093506
>>> timeit('x ** 2', 'x = 42', number=10**7)
0.7093241214752197

# Python 3.5.2
>>> timeit('x * x', 'x = 42', number=10**7)
0.5049805610033218
>>> timeit('x ** 2', 'x = 42', number=10**7)
3.6540668540110346
``````

It's very surprising to me that:

1. python2 is faster than python3 in this operation consistently
2. my benchmark result is quite different from yours
3. python3 seems to do worse optimization on exponential operations.

• @voiceup Quite interesting, yes, especially how very slow Python 3 is with `x ** 2`. My above tests were with Python 2 because that's what LeetCode uses. Now I ran some more tests:

Python 2.7.11:

``````>>> [int(100 * timeit('x * x', 'x = 42', number=10**7)) for _ in range(10)]
[36, 35, 35, 36, 38, 36, 35, 35, 35, 35]
>>> [int(100 * timeit('x**2', 'x = 42', number=10**7)) for _ in range(10)]
[36, 35, 37, 36, 35, 36, 36, 35, 35, 36]
``````

Python 3.5.1:

``````>>> [int(100 * timeit('x * x', 'x = 42', number=10**7)) for _ in range(10)]
[48, 48, 48, 47, 48, 48, 48, 48, 48, 50]
>>> [int(100 * timeit('x**2', 'x = 42', number=10**7)) for _ in range(10)]
[194, 190, 196, 184, 198, 183, 194, 187, 196, 188]
``````

• @StefanPochmann Thanks for your help, and I'm a beginner of Python. I do not understand how to use "for in" like this. Could you pls explain the syntax.
PS:I know use "for...in.." like this:
def numberOfBoomerangs(self, points):
return sum([sum(n*(n-1) for n in collections.Counter([(x1-x2)**2 + (y1-y2)**2
for x2, y2 in points]).values())
for x1, y1 in points])

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.