Given an array and two integers say, x and y, find the number of sub-arrays in which the number of occurrences of x is equal to number of occurrences of y.
Example 1:
Input:
n = 4, x = 1, y = 2
arr[] = {1, 2, 1}
Output: 2
Explanation:
The possible sub-arrays have same equal 
number of occurrences of x and y are:
1) {1, 2}, x and y have same occurrence(1).
2) {2, 1}, x and y have same occurrence(1).
Example 2:
Input:
n = 5, x = 4, y = 6
arr[] = {1, 2, 1}
Output: 6
Explanation:
The possible sub-arrays have same equal 
number of occurrences of x and y are:
1) {1}, x and y have same occurrence(0).
2) {2}, x and y have same occurrence(0).
3) {1}, x and y have same occurrence(0).
4) {1, 2}, x and y have same occurrence(0).
5) {2, 1}, x and y have same occurrence(0).
6) {1, 2, 1}, x and y have same occurrence(0).
Your Task:
You don't need to read input or print anything. Your task is to complete the function sameOccurrence() which takes the array of integers arr, n, x and y as parameters and returns an integer denoting the answer.
Expected Time Complexity: O(n)
Expected Auxiliary Space: O(n)
Constraints: 
1 <= n <= 10^{5}
1 <= arr[i], x, y<=10^{6}

Source: geeksforgeeks | Difficulty: EASY
Tags: Data structures

Starter code: #User function Template for python3



class Solution:
    def sameOccurrence(self, arr, n, x, y):
        # code here

Solutions:
class Solution:

	def sameOccurrence(self, arr, n, x, y):
		if x == y:
			return n * (n + 1) // 2
		diff = 0
		diffToCnt = {}
		diffToCnt[0] = 1
		ans = 0
		for num in arr:
			if num == x:
				diff += 1
			elif num == y:
				diff -= 1
			if diff in diffToCnt:
				ans += diffToCnt[diff]
			if diff not in diffToCnt:
				diffToCnt[diff] = 0
			diffToCnt[diff] += 1
		return ans


from collections import defaultdict as dd

class Solution:

	def sameOccurrence(self, arr, n, x, y):
		d = dd(lambda : 0)
		d[0] = 1
		count = 0
		output = 0
		for item in arr:
			count += item == x
			count -= item == y
			output += d[count]
			d[count] += 1
		return output


class Solution:

	def sameOccurrence(self, arr, n, x, y):
		countx = 0
		county = 0
		d = {0: 1}
		res = 0
		for i in arr:
			if i == x:
				countx += 1
			if i == y:
				county += 1
			diff = countx - county
			if diff in d:
				res += d[diff]
				d[diff] += 1
			else:
				d[diff] = 1
		return res


from collections import defaultdict

class Solution:

	def sameOccurrence(self, arr, n, x, y):
		c_x = 0
		c_y = 0
		hashmap = defaultdict(int)
		hashmap[0] = 1
		count = 0
		for num in arr:
			if num == x:
				c_x += 1
			if num == y:
				c_y += 1
			count += hashmap[c_x - c_y]
			hashmap[c_x - c_y] += 1
		return count
if __name__ == '__main__':
	tc = int(input())
	while tc > 0:
		(n, x, y) = list(map(int, input().strip().split()))
		arr = list(map(int, input().strip().split()))
		ans = Solution().sameOccurrence(arr, n, x, y)
		print(ans)
		tc -= 1


from collections import Counter

class Solution:

	def sameOccurrence(self, a, n, x, y):
		ar = [0]
		cx = [0]
		cy = [0]
		for i in range(n):
			if a[i] == x:
				cx.append(cx[-1] + 1)
			else:
				cx.append(cx[-1])
			if a[i] == y:
				cy.append(cy[-1] + 1)
			else:
				cy.append(cy[-1])
		m = Counter()
		for i in range(1, n + 1):
			m[cx[i] - cy[i]] += 1
		ans = m[0]
		for i in m:
			ans += m[i] * (m[i] - 1) // 2
		return ans


class Solution:

	def sameOccurrence(self, arr, n, x, y):
		if x == y:
			ans = int(n * (n + 1) / 2)
			return ans
		for i in range(n):
			if arr[i] == x:
				arr[i] = 1
			elif arr[i] == y:
				arr[i] = -1
			else:
				arr[i] = 0
		listed = {}
		listed[0] = 1
		if arr[0] in listed:
			listed[arr[0]] += 1
		else:
			listed[arr[0]] = 1
		for i in range(1, n):
			arr[i] += arr[i - 1]
			if arr[i] in listed:
				listed[arr[i]] += 1
			else:
				listed[arr[i]] = 1
		ans = 0
		for x in listed:
			c = listed[x]
			ans += int(c * (c - 1) / 2)
		return ans