In a given cartesian plane, there are N points. We need to find the Number of Pairs of  points(A, B) such that
	Point A and Point B do not coincide.
	Manhattan Distance and the Euclidean Distance between the points should be equal.
Note: Pair of 2 points(A,B) is considered different from  Pair of 2 points(B ,A).
Manhattan Distance = |x2-x1|+|y2-y1|
Euclidean Distance   = ((x2-x1)^2 + (y2-y1)^2)^0.5, where points are (x1,y1) and (x2,y2).
 
Example 1:
Input:
N = 2
X = {1, 7}
Y = {1, 5}
Output:
0
Explanation:
None of the pairs of points have
equal Manhatten and Euclidean distance.
Example 2:
Input:
N = 3
X = {1, 2, 1}
Y = {2, 3, 3}
Output:
2
Explanation:
The pairs {(1,2), (1,3)}, and {(1,3), (2,3)}
have equal Manhatten and Euclidean distance.
 
Your Task:
You don't need to read input or print anything. Your task is to complete the function numOfPairs() which takes an Integer N and two arrays X, and Y of length N as input and returns the number of pairs with equal Manhattan and Euclidean Distance. (X[i], Y[i]) denotes a point.
 
Expected Time Complexity: O(N)
Expected Auxiliary Space: O(N)
 
Constraints:
1 <= N <= 10^{5}
 -10^9 <= X[i], Y[i] <= 10^9

Source: geeksforgeeks | Difficulty: MEDIUM
Tags: String algorithms

Data structures

Mathematics

Starter code: #User function Template for python3



class Solution:

    def numOfPairs(self, X, Y, N):

        # code here 

Solutions:
class Solution:

	def numOfPairs(self, X, Y, N):
		ans = 0
		xMap = {}
		yMap = {}
		xyMap = {}
		for i in range(N):
			x = X[i]
			y = Y[i]
			xValue = xMap.get(x, 0)
			yValue = yMap.get(y, 0)
			comb = str(x) + '*' + str(y)
			xyValue = xyMap.get(comb, 0)
			ans += xValue + yValue - 2 * xyValue
			xMap[x] = xValue + 1
			yMap[y] = yValue + 1
			xyMap[comb] = xyValue + 1
		return ans


class Solution:

	def numOfPairs(self, X, Y, N):
		(dict1, dict2) = ({}, {})
		equal = {}
		ans = 0
		for i in range(N):
			temp = dict1.get(X[i], 0)
			ans += temp
			dict1[X[i]] = temp + 1
			temp = dict2.get(Y[i], 0)
			ans += temp
			dict2[Y[i]] = temp + 1
			d = X[i] * (10 ** 9 + 1) + Y[i]
			temp = equal.get(d, 0)
			ans -= 2 * temp
			equal[d] = temp + 1
		return ans


from collections import defaultdict

class Solution:

	def numOfPairs(self, Xx, Yy, n):
		X = defaultdict(lambda : 0)
		Y = defaultdict(lambda : 0)
		XY = defaultdict(lambda : 0)
		for i in range(0, n):
			xi = Xx[i]
			yi = Yy[i]
			X[xi] += 1
			Y[yi] += 1
			XY[Xx[i], Yy[i]] += 1
		(xAns, yAns, xyAns) = (0, 0, 0)
		for xCoordinatePair in X:
			xFrequency = X[xCoordinatePair]
			sameXPairs = xFrequency * (xFrequency - 1) // 2
			xAns += sameXPairs
		for yCoordinatePair in Y:
			yFrequency = Y[yCoordinatePair]
			sameYPairs = yFrequency * (yFrequency - 1) // 2
			yAns += sameYPairs
		for XYPair in XY:
			xyFrequency = XY[XYPair]
			samePointPairs = xyFrequency * (xyFrequency - 1) // 2
			xyAns += samePointPairs
		return xAns + yAns - 2 * xyAns


from collections import defaultdict

class Solution:

	def numOfPairs(self, X, Y, N):
		xc = defaultdict(int)
		yc = defaultdict(int)
		xyc = defaultdict(int)
		cnt = 0
		for (x, y) in zip(X, Y):
			cnt += xc[x] + yc[y] - xyc[x, y] * 2
			xc[x] += 1
			yc[y] += 1
			xyc[x, y] += 1
		return cnt


import time
from collections import defaultdict

class Solution:

	def numOfPairs(self, X1, Y1, N):
		X = {}
		Y = {}
		XY = {}
		for i in range(N):
			xi = X1[i]
			yi = Y1[i]
			if xi in X:
				X[xi] += 1
			else:
				X[xi] = 1
			if yi in Y:
				Y[yi] += 1
			else:
				Y[yi] = 1
			if (xi, yi) in XY:
				XY[xi, yi] += 1
			else:
				XY[xi, yi] = 1
		xAns = 0
		yAns = 0
		xyAns = 0
		for xCoordinatePair in X.items():
			xFrequency = xCoordinatePair[1]
			sameXPairs = xFrequency * (xFrequency - 1) // 2
			xAns += sameXPairs
		for yCoordinatePair in Y.items():
			yFrequency = yCoordinatePair[1]
			sameYPairs = yFrequency * (yFrequency - 1) // 2
			yAns += sameYPairs
		for XYPair in XY.items():
			xyFrequency = XYPair[1]
			samePointPairs = xyFrequency * (xyFrequency - 1) // 2
			xyAns += samePointPairs
		return xAns + yAns - 2 * xyAns


class Solution:

	def numOfPairs(self, X, Y, n):
		hmapx = {}
		hmapy = {}
		hmapxy = {}
		ans = 0
		for i in range(n):
			if X[i] in hmapx:
				ans += hmapx[X[i]]
				hmapx[X[i]] += 1
			else:
				hmapx[X[i]] = 1
			if Y[i] in hmapy:
				ans += hmapy[Y[i]]
				hmapy[Y[i]] += 1
			else:
				hmapy[Y[i]] = 1
			if str(X[i]) + '*' + str(Y[i]) in hmapxy:
				ans -= 2 * hmapxy[str(X[i]) + '*' + str(Y[i])]
				hmapxy[str(X[i]) + '*' + str(Y[i])] += 1
			else:
				hmapxy[str(X[i]) + '*' + str(Y[i])] = 1
		return ans


class Solution:

	def numOfPairs(self, X, Y, N):
		xmap = {}
		ymap = {}
		xymap = {}
		sum = 0
		for i in range(N):
			x = X[i]
			y = Y[i]
			xy = str(x) + '*' + str(y)
			xmap[x] = xmap.get(x, 0) + 1
			ymap[y] = ymap.get(y, 0) + 1
			xymap[xy] = xymap.get(xy, 0) + 1
			sum += xmap[x] + ymap[y] - 2 * xymap[xy]
		return sum


from collections import Counter

class Solution:

	def numOfPairs(self, X, Y, N):
		xfreq = Counter(X)
		yfreq = Counter(Y)
		res = 0
		for (_, x) in xfreq.items():
			res += x * (x - 1) // 2
		for (_, y) in yfreq.items():
			res += y * (y - 1) // 2
		xyres = 0
		xymap = {}
		for i in range(N):
			xymap[X[i], Y[i]] = xymap.get((X[i], Y[i]), 0) + 1
		for (_, xy) in xymap.items():
			xyres += xy * (xy - 1) // 2
		return res - 2 * xyres


from collections import Counter

class Solution:

	def numOfPairs(self, X, Y, N):
		both_points = [sorted(zip(X, Y)), sorted(zip(Y, X))]
		total = 0
		for points in both_points:
			current = 0
			repeat = 0
			for i in range(1, N):
				if points[i][0] == points[i - 1][0]:
					current += 1
					total += current
					if points[i][1] == points[i - 1][1]:
						repeat += 1
						total -= repeat
					else:
						repeat = 0
				else:
					current = 0
					repeat = 0
		return total


class Solution:

	def numOfPairs(self, X, Y, N):
		ans = 0
		dx = {}
		dy = {}
		dxy = {}
		for i in range(N):
			(x, y) = (X[i], Y[i])
			if x in dx:
				ans += dx[x]
				dx[x] += 1
			else:
				dx[x] = 1
			if y in dy:
				ans += dy[y]
				dy[y] += 1
			else:
				dy[y] = 1
			if (x, y) in dxy:
				ans -= 2 * dxy[x, y]
				dxy[x, y] += 1
			else:
				dxy[x, y] = 1
		return ans


from collections import defaultdict

class Solution:

	def numOfPairs(self, X, Y, N):
		(x, y) = (defaultdict(int), defaultdict(int))
		pair = defaultdict(int)
		(ans, ans1) = (0, 0)
		for i in range(N):
			x[X[i]] += 1
			y[Y[i]] += 1
			pair[X[i], Y[i]] += 1
			ans += x[X[i]]
			ans += y[Y[i]]
			ans1 += pair[X[i], Y[i]]
		return ans - 2 * ans1


class Solution:

	def numOfPairs(self, X, Y, N):
		(dictY, dictX) = ({}, {})
		dictXY = {}
		res = 0
		for i in range(N):
			if X[i] not in dictX:
				dictX[X[i]] = 1
			else:
				dictX[X[i]] += 1
			if Y[i] not in dictY:
				dictY[Y[i]] = 1
			else:
				dictY[Y[i]] += 1
			Str = str(X[i]) + '*' + str(Y[i])
			if Str not in dictXY:
				dictXY[Str] = 1
			else:
				dictXY[Str] += 1
			res += dictX[X[i]] + dictY[Y[i]] - 2 * dictXY[Str]
		return res


class Solution:

	def numOfPairs(self, X, Y, n):
		xhash = dict()
		yhash = dict()
		res = 0
		i = 0
		while i < n:
			(x, y) = (X[i], Y[i])
			if x in xhash:
				for ind in xhash[x]:
					if Y[ind] != y:
						res += 1
			else:
				xhash[x] = []
			xhash[x].append(i)
			if y in yhash:
				for ind in yhash[y]:
					if X[ind] != x:
						res += 1
			else:
				yhash[y] = []
			yhash[y].append(i)
			i += 1
		return res


from collections import Counter

class Solution:

	def numOfPairs(self, X, Y, N):
		xseen = Counter()
		yseen = Counter()
		seen = set()
		same = 0
		for i in range(N):
			xseen[X[i]] += 1
			yseen[Y[i]] += 1
			if (X[i], Y[i]) in seen:
				same += 2
			else:
				seen.add((X[i], Y[i]))
		ans = 0
		for (k, v) in xseen.items():
			ans += v * (v - 1) // 2
		for (k, v) in yseen.items():
			ans += v * (v - 1) // 2
		return ans - same


from collections import defaultdict

class Solution:

	def numOfPairs(self, x, y, n):
		(xmp, ymp) = (defaultdict(lambda : 0), defaultdict(lambda : 0))
		same = defaultdict(lambda : 0)
		for i in range(n):
			xmp[x[i]] += 1
			ymp[y[i]] += 1
			same[x[i], y[i]] += 1
		ans = 0
		for cnt in xmp.values():
			ans += cnt * (cnt - 1) // 2
		for cnt in ymp.values():
			ans += cnt * (cnt - 1) // 2
		for cnt in same.values():
			ans -= cnt * (cnt - 1)
		return ans


class Solution:

	def numOfPairs(self, X, Y, N):
		ans = 0
		x = {}
		y = {}
		pair = {}
		for i in range(N):
			if X[i] in x:
				ans += x[X[i]]
				x[X[i]] = x[X[i]] + 1
			else:
				x[X[i]] = 1
			if Y[i] in y:
				ans += y[Y[i]]
				y[Y[i]] = y[Y[i]] + 1
			else:
				y[Y[i]] = 1
			if (X[i], Y[i]) in pair:
				ans = ans - 2 * pair[X[i], Y[i]]
				pair[X[i], Y[i]] = pair[X[i], Y[i]] + 1
			else:
				pair[X[i], Y[i]] = 1
		return ans


class Solution:

	def numOfPairs(self, X, Y, N):
		mapx = {}
		mapy = {}
		mapxy = {}
		ans = 0
		for i in range(N):
			if X[i] in mapx:
				ans += mapx[X[i]]
				mapx[X[i]] += 1
			else:
				mapx[X[i]] = 1
			if Y[i] in mapy:
				ans += mapy[Y[i]]
				mapy[Y[i]] += 1
			else:
				mapy[Y[i]] = 1
			a = str(X[i])
			b = str(Y[i])
			if str(a + '-' + b) in mapxy:
				ans -= 2 * mapxy[str(a + '-' + b)]
				mapxy[str(a + '-' + b)] += 1
			else:
				mapxy[str(a + '-' + b)] = 1
		return ans


import math

class Solution:

	def numOfPairs(self, X, Y, N):
		hmapx = {}
		hmapy = {}
		hmapxy = {}
		ans = 0
		for i in range(N):
			if X[i] in hmapx:
				ans += hmapx[X[i]]
				hmapx[X[i]] += 1
			else:
				hmapx[X[i]] = 1
			if Y[i] in hmapy:
				ans += hmapy[Y[i]]
				hmapy[Y[i]] += 1
			else:
				hmapy[Y[i]] = 1
			if str(X[i]) + '*' + str(Y[i]) in hmapxy:
				ans -= 2 * hmapxy[str(X[i]) + '*' + str(Y[i])]
				hmapxy[str(X[i]) + '*' + str(Y[i])] += 1
			else:
				hmapxy[str(X[i]) + '*' + str(Y[i])] = 1
		return ans


from collections import defaultdict

class Solution:

	def numOfPairs(self, x, y, n):
		hmapx = {}
		hmapy = {}
		hmapxy = {}
		ans = 0
		for i in range(n):
			if X[i] in hmapx:
				ans += hmapx[X[i]]
				hmapx[X[i]] += 1
			else:
				hmapx[X[i]] = 1
			if Y[i] in hmapy:
				ans += hmapy[Y[i]]
				hmapy[Y[i]] += 1
			else:
				hmapy[Y[i]] = 1
			if str(X[i]) + '*' + str(Y[i]) in hmapxy:
				ans -= 2 * hmapxy[str(X[i]) + '*' + str(Y[i])]
				hmapxy[str(X[i]) + '*' + str(Y[i])] += 1
			else:
				hmapxy[str(X[i]) + '*' + str(Y[i])] = 1
		return ans


from collections import defaultdict

class Solution:

	def numOfPairs(self, X, Y, N):
		q = defaultdict(int)
		p = defaultdict(int)
		d = defaultdict(int)
		c = 0
		for (i, j) in zip(X, Y):
			c += p[i] + q[j] - d[i, j] * 2
			p[i] += 1
			q[j] += 1
			d[i, j] += 1
		return c


from collections import defaultdict

class Solution:

	def numOfPairs(self, X, Y, N):
		x = defaultdict(lambda : 0)
		y = defaultdict(lambda : 0)
		xy = defaultdict(lambda : 0)
		for i in range(N):
			x[X[i]] += 1
			y[Y[i]] += 1
			t = (X[i], Y[i])
			xy[t] += 1
		(xA, yA, xyA) = (0, 0, 0)
		for cp1 in x:
			xA += x[cp1] * (x[cp1] - 1) // 2
		for cp2 in y:
			yA += y[cp2] * (y[cp2] - 1) // 2
		for cp3 in xy:
			xyA += xy[cp3] * (xy[cp3] - 1) // 2
		return xA + yA - 2 * xyA


from collections import defaultdict

class Solution:

	def numOfPairs(self, X, Y, N):
		(xfreq, yfreq) = (defaultdict(int), defaultdict(int))
		xyfreq = defaultdict(int)
		ans = 0
		for i in range(N):
			(x, y) = (X[i], Y[i])
			xy = (x, y)
			ans += xfreq[x] + yfreq[y] - 2 * xyfreq[xy]
			xfreq[x] += 1
			yfreq[y] += 1
			xyfreq[xy] += 1
		return ans


import math

class Solution:

	def numOfPairs(self, X, Y, N):
		d1 = {}
		d2 = {}
		d3 = {}
		res = 0
		c = 0
		res1 = 0
		for i in range(N):
			if X[i] in d1.keys():
				d1[X[i]] += 1
			else:
				d1[X[i]] = 1
			if Y[i] in d2.keys():
				d2[Y[i]] += 1
			else:
				d2[Y[i]] = 1
			if (X[i], Y[i]) in d3.keys():
				d3[X[i], Y[i]] += 1
			else:
				d3[X[i], Y[i]] = 1
		for i in d1.keys():
			if d1[i] > 1:
				res += math.factorial(d1[i]) // (math.factorial(d1[i] - 2) * 2)
		for i in d2.keys():
			if d2[i] > 1:
				res += math.factorial(d2[i]) // (math.factorial(d2[i] - 2) * 2)
		for i in d3.keys():
			if d3[i] > 1:
				res1 += math.factorial(d3[i]) // (math.factorial(d3[i] - 2) * 2)
		return res - 2 * res1


from collections import defaultdict

class Solution:

	def numOfPairs(self, X, Y, N):
		c = 0
		m = defaultdict(int)
		n = defaultdict(int)
		o = defaultdict(int)
		for (x, y) in zip(X, Y):
			c += m[x] + n[y] - o[x, y] * 2
			m[x] += 1
			n[y] += 1
			o[x, y] += 1
		return c


from collections import defaultdict

class Solution:

	def numOfPairs(self, X, Y, N):
		p1 = defaultdict(int)
		p2 = defaultdict(int)
		d = defaultdict(int)
		ans = 0
		for i in range(N):
			ans += p1[X[i]] + p2[Y[i]] - 2 * d[X[i], Y[i]]
			d[tuple([X[i], Y[i]])] += 1
			p1[X[i]] += 1
			p2[Y[i]] += 1
		return ans


class Solution:

	def xCollinearPoints(self, point, point_set):
		pass

	def yCollinearPoints(self, point, point_set):
		pass

	def collinearPoints(self, reference_point, point_set):
		collinear_points = 0
		points_to_remove = {reference_point}
		for point in point_set:
			if point == reference_point:
				continue
			if point[0] == reference_point[0] or point[1] == reference_point[1]:
				collinear_points += 1
				points_to_remove.add(point)
		for point in points_to_remove:
			point_set.remove(point)
		return collinear_points

	def getPairCount(self, coordinate_freq):
		pair_count = 0
		for val in coordinate_freq.values():
			pair_count += val - 1
		return pair_count

	def numOfPairs(self, X, Y, N):
		x_coordinate_freq = {}
		y_coordinate_freq = {}
		xy_coordinate_freq = {}
		ans = 0
		for (x, y) in zip(X, Y):
			x_coordinate_freq[x] = x_coordinate_freq.get(x, 0)
			ans += x_coordinate_freq[x]
			x_coordinate_freq[x] += 1
			y_coordinate_freq[y] = y_coordinate_freq.get(y, 0)
			ans += y_coordinate_freq[y]
			y_coordinate_freq[y] += 1
			xy_coordinate_freq[x, y] = xy_coordinate_freq.get((x, y), 0)
			ans -= 2 * xy_coordinate_freq[x, y]
			xy_coordinate_freq[x, y] += 1
		return ans


from collections import defaultdict as dd

class Solution:

	def numOfPairs(self, x, y, n):
		xc = dd(int)
		yc = dd(int)
		c = dd(int)
		cnt = 0
		for i in range(n):
			cnt += xc[x[i]] + yc[y[i]] - c[x[i], y[i]] * 2
			xc[x[i]] += 1
			yc[y[i]] += 1
			c[x[i], y[i]] += 1
		return cnt


from collections import defaultdict

class Solution:

	def numOfPairs(self, X, Y, N):

		def sel():
			return 0
		arx = defaultdict(sel)
		ary = defaultdict(sel)
		com = defaultdict(sel)
		ans = 0
		for (x, y) in zip(X, Y):
			ans += arx[x] + ary[y] - com[x, y] * 2
			arx[x] += 1
			ary[y] += 1
			com[x, y] += 1
		return ans


from collections import defaultdict as dd

class Solution:

	def numOfPairs(self, X, Y, N):
		x_freq = dd(int)
		y_freq = dd(int)
		tracker = dd(int)
		ans = 0
		for i in range(len(X)):
			ans += x_freq[X[i]] + y_freq[Y[i]] - tracker[X[i], Y[i]] * 2
			x_freq[X[i]] += 1
			y_freq[Y[i]] += 1
			tracker[X[i], Y[i]] += 1
		return int(ans)


from collections import *

class Solution:

	def numOfPairs(self, x, y, n):
		s = set()
		ans = 0
		d = defaultdict(int)
		p = defaultdict(int)
		for i in range(n):
			ans += d[x[i]] + p[y[i]] - 2 * d[x[i], y[i]]
			d[x[i]] += 1
			p[y[i]] += 1
			d[x[i], y[i]] += 1
		return ans


from collections import defaultdict

class Solution:

	def numOfPairs(self, x, y, n):
		x1 = defaultdict(int)
		y1 = defaultdict(int)
		xy = defaultdict(int)
		c = 0
		for (i, j) in zip(x, y):
			c += x1[i] + y1[j] - xy[i, j] * 2
			x1[i] += 1
			y1[j] += 1
			xy[i, j] += 1
		return c


from collections import *

class Solution:

	def numOfPairs(self, X, Y, N):
		(ma, mb, mc) = (Counter(), Counter(), Counter())
		for (x, y) in zip(X, Y):
			ma[x] += 1
			mb[y] += 1
			mc[x, y] += 1
		res = 0
		for (k, v) in ma.items():
			res += v * (v - 1) // 2
		for (k, v) in mb.items():
			res += v * (v - 1) // 2
		for (k, v) in mc.items():
			res -= 2 * (v * (v - 1) // 2)
		return res


from collections import defaultdict

class Solution:

	def numOfPairs(self, X, Y, N):
		x_dic = defaultdict(list)
		y_dic = defaultdict(list)
		same = defaultdict(int)
		for (i, j) in zip(X, Y):
			x_dic[i].append(j)
			y_dic[j].append(i)
			same[i, j] += 1
		count = 0
		for (i, val) in x_dic.items():
			if len(val) > 1:
				count += len(val) * (len(val) - 1) // 2
		for (i, val) in y_dic.items():
			if len(val) > 1:
				count += len(val) * (len(val) - 1) // 2
		for (i, val) in same.items():
			if val > 1:
				count -= val
		return count


from collections import Counter

class Solution:

	def numOfPairs(self, X, Y, N):
		a = Counter()
		b = Counter()
		c = set()
		same = 0
		for i in range(N):
			a[X[i]] += 1
			b[Y[i]] += 1
			if (X[i], Y[i]) in c:
				same += 2
			else:
				c.add((X[i], Y[i]))
		soln = 0
		for (k, v) in a.items():
			soln += v * (v - 1) // 2
		for (k, v) in b.items():
			soln += v * (v - 1) // 2
		return soln - same


from collections import defaultdict

class Solution:

	def numOfPairs(self, X, Y, N):
		x = {}
		y = {}
		xy = {}
		pairs = 0
		for (a, b) in zip(X, Y):
			x_frequecy = x.get(a, 0)
			y_frequecy = y.get(b, 0)
			xy_freqeucy = xy.get((a, b), 0)
			pairs = pairs + (x_frequecy + y_frequecy - xy_freqeucy * 2)
			if a in x:
				x[a] += 1
			else:
				x[a] = 1
			if b in y:
				y[b] += 1
			else:
				y[b] = 1
			if (a, b) in xy:
				xy[a, b] += 1
			else:
				xy[a, b] = 1
		return pairs