C++ Cached and Uncached versions.

• Uncached version. Time complexity is `O(n^2)`.

31 / 31 test cases passed
Status: Accepted
Runtime: 906 ms

``````class Solution {
public:
int numberOfBoomerangs(vector<pair<int, int>>& points) {
uint siz = points.size(), cnt = 0;
unordered_map<uint, uint> map;
map.reserve(siz);
for (uint i = 0; i < siz; i++) {
for (uint j = 0; j < siz; j++) {
if (i == j) continue;
uint dis = pow(points[j].first - points[i].first, 2) + pow(points[j].second - points[i].second, 2);
cnt += 2 * map[dis]++;
}
map.clear();
}
return cnt;
}
};
``````

Cached version. Not too much difference though. Time complexity is still `O(n^2)`.

31 / 31 test cases passed
Status: Accepted
Runtime: 846 ms

``````class Solution {
public:
int numberOfBoomerangs(vector<pair<int, int>>& points) {
uint siz = points.size(), cnt = 0;
vector<vector<uint>> v(siz, vector<uint>(siz));
unordered_map<uint, uint> map;
map.reserve(siz);
for (uint i = 0; i < siz; i++) {
for (uint j = i+1; j < siz; j++) {
uint dis = pow(points[j].first - points[i].first, 2) + pow(points[j].second - points[i].second, 2);
v[i][j] = v[j][i] = dis;
}
}
for (uint i = 0; i < siz; i++) {
for (uint j = 0; j < siz; j++) {
if (i == j) continue;
cnt += 2 * map[v[i][j]]++;
}
map.clear();
}
return cnt;
}
};
``````

Unfortunately this version gets MLE when input size is huge.

``````class Solution {
public:
int numberOfBoomerangs(vector<pair<int, int>>& points) {
uint siz = points.size(), cnt = 0;
unordered_map<unsigned long long, uint> map;
map.reserve(siz * (siz - 1));
for (uint i = 0; i < siz; i++) {
for (uint j = i+1; j < siz; j++) {
uint dis = pow(points[j].first - points[i].first, 2) + pow(points[j].second - points[i].second, 2);
unsigned long long hash = (unsigned long long)dis << 32 | i;
cnt += 2 * map[hash]++;
hash = (unsigned long long)dis << 32 | j;
cnt += 2 * map[hash]++;
}
}
return cnt;
}
};
``````

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