Given an array, if ‘n’ positive integers, count the number of pairs of integers in the array that have the sum divisible by 4. 
Example 1:
Input : Arr[] = {2, 2, 1, 7, 5}
Output : 3
Explanation:
(2,2), (1,7) and(7,5) are the 3 pairs.
Example 2:
Input : Arr[] = {2, 2, 3, 5, 6}
Output : 4
 
Your Task:
This is a function problem. The input is already taken care of by the driver code. You only need to complete the function count4Divisibiles() that takes an array (arr), sizeOfArray (n), and return the number of pairs. The driver code takes care of the printing.
Expected Time Complexity: O(N).
Expected Auxiliary Space: O(1).
Constraints:
1 ≤ N ≤ 10^{5}
1 ≤ arr[] ≤ 10^{5}

Source: geeksforgeeks | Difficulty: EASY
Tags: Data structures

Starter code: #User function Template for python3

class Solution:
    def count4Divisibiles(self, arr , n ): 
          
        # Complete the function

Solutions:
class Solution:

	def count4Divisibiles(self, arr, n):
		arr.sort()
		rem = [0] * 4
		for index in range(n):
			rem[arr[index] % 4] += 1
		ans = 0
		ans += rem[0] * (rem[0] - 1) // 2
		ans += rem[2] * (rem[2] - 1) // 2
		ans += rem[1] * rem[3]
		return ans


class Solution:

	def count4Divisibiles(self, arr, n):
		pairs = 0
		freq = [0] * 4
		for x in arr:
			rem = x % 4
			pairs += freq[(4 - rem) % 4]
			freq[rem] += 1
		return pairs


class Solution:

	def count4Divisibiles(self, arr, n):
		freq = [0, 0, 0, 0]
		for i in range(n):
			freq[arr[i] % 4] += 1
		ans = freq[0] * (freq[0] - 1) // 2
		ans += freq[2] * (freq[2] - 1) // 2
		ans += freq[1] * freq[3]
		return int(ans)


class Solution:

	def count4Divisibiles(self, arr, n):
		ans = 0
		freq = [0] * 4
		for i in arr:
			rem = i % 4
			ans += freq[(4 - rem) % 4]
			freq[rem] += 1
		return ans


class Solution:

	def count4Divisibiles(self, arr, n):
		d = {}
		ans = 0
		for i in arr:
			a = i % 4
			if 4 - a in d:
				ans += d[4 - a]
			if a == 0:
				if 0 in d:
					ans += d[0]
			if a not in d:
				d[a] = 1
			else:
				d[a] += 1
		return ans


from collections import Counter

class Solution:

	def count4Divisibiles(self, arr, n):
		for i in range(n):
			arr[i] = arr[i] % 4
		c = Counter(arr)
		count = 0
		if c[0] > 0:
			count += c[0] * (c[0] - 1) // 2
		count += c[1] * c[3]
		if c[2] > 0:
			count += c[2] * (c[2] - 1) // 2
		return count


class Solution:

	def count4Divisibiles(self, arr, n):
		d = {}
		co = 0
		for i in arr:
			k = i % 4
			if 4 - k in d:
				co += d[4 - k]
			if k == 0:
				if 0 in d:
					co += d[0]
			if k not in d:
				d[k] = 1
			else:
				d[k] += 1
		return co


class Solution:

	def count4Divisibiles(self, arr, n):
		a = 0
		b = 0
		c = 0
		d = 0
		total = 0
		for i in range(n):
			if arr[i] % 4 == 1:
				a += 1
			elif arr[i] % 4 == 2:
				b += 1
			elif arr[i] % 4 == 3:
				c += 1
			else:
				d += 1
		total += d * (d - 1) // 2
		total += b * (b - 1) // 2
		total += a * c
		return total


class Solution:

	def count4Divisibiles(self, arr, n):
		h = 0
		f = [0] * 4
		for i in arr:
			r = i % 4
			h += f[(4 - r) % 4]
			f[r] += 1
		return h


class Solution:

	def count4Divisibiles(self, arr, n):
		s = {}
		for i in range(4):
			s[i] = 0
		for i in arr:
			s[i % 4] += 1
		c = s[0] * (s[0] - 1) // 2
		d = 2
		if 4 % 2 == 0:
			c += s[d] * (s[d] - 1) // 2
			d = d - 1
		for i in range(1, 2):
			c += s[i] * s[4 - i]
		return c


class Solution:

	def count4Divisibiles(self, arr, n):
		rem = [0] * 4
		res = 0
		for i in range(n):
			rem_pos = arr[i] % 4
			rem[rem_pos] += 1
		res += rem[0] * (rem[0] - 1) // 2
		res += rem[2] * (rem[2] - 1) // 2
		res += rem[1] * rem[3]
		return res


from collections import defaultdict

class Solution:

	def count4Divisibiles(self, arr, n):
		d = defaultdict(list)
		for (i, v) in enumerate(arr):
			d[v & 3] += (v,)
		return (len(d[0]) * (len(d[0]) - 1) >> 1) + (len(d[2]) * (len(d[2]) - 1) >> 1) + len(d[1]) * len(d[3])


class Solution:

	def count4Divisibiles(self, a, n):
		count = 0
		d = {}
		for i in range(n):
			rem = a[i] % 4
			t = (4 - rem) % 4
			count += d.get(t, 0)
			d[rem] = d.get(rem, 0) + 1
		return count


class Solution:

	def count4Divisibiles(self, arr, n):
		freqs = {}
		cnt = 0
		for i in range(n):
			num = arr[i] % 4
			if (4 - arr[i]) % 4 in freqs:
				cnt += freqs[(4 - arr[i]) % 4]
			if num not in freqs:
				freqs[num] = 1
			else:
				freqs[num] += 1
		return cnt


class Solution:

	def count4Divisibiles(self, arr, n):
		k = 4
		temp = [0] * k
		for i in range(n):
			index = arr[i] % k
			temp[index] += 1
		count = 0
		for i in range(1, k // 2):
			count += temp[i] * temp[k - i]
		if temp[0] != 0:
			count += temp[0] * (temp[0] - 1) // 2
		if temp[k // 2] != 0:
			count += temp[k // 2] * (temp[k // 2] - 1) // 2
		return count


class Solution:

	def count4Divisibiles(self, arr, n):
		p = 0
		l = [0] * 4
		for i in arr:
			z = i % 4
			p += l[(4 - z) % 4]
			l[z] += 1
		return p


from itertools import combinations

class Solution:

	def count4Divisibiles(self, arr, n):
		d = {}
		count = 0
		for i in arr:
			if (4 - i % 4) % 4 in d:
				count += d[(4 - i % 4) % 4]
			if i % 4 not in d:
				d[i % 4] = 1
			else:
				d[i % 4] += 1
		return count


class Solution:

	def count4Divisibiles(self, a, n):
		count = [0, 0, 0, 0]
		for i in range(n):
			count[a[i] % 4] += 1
		ans = (count[0] - 1) * count[0] // 2 + count[1] * count[3] + (count[2] - 1) * count[2] // 2
		return ans


from collections import defaultdict

class Solution:

	def count4Divisibiles(self, arr, n):
		d = dict()
		for i in range(len(arr)):
			if arr[i] % 4 not in d:
				d[arr[i] % 4] = 1
			else:
				d[arr[i] % 4] += 1
		k = 0
		for i in range(len(arr)):
			if arr[i] % 4 == 0:
				k += d[arr[i] % 4] - 1
				continue
			if 4 - arr[i] % 4 in d:
				k += d[4 - arr[i] % 4]
				if arr[i] % 4 == 4 - arr[i] % 4:
					k -= 1
		return k // 2


class Solution:

	def count4Divisibiles(self, a, n):
		d = dict()
		for i in range(len(a)):
			if a[i] % 4 not in d:
				d[a[i] % 4] = 1
			else:
				d[a[i] % 4] += 1
		k = 0
		for i in range(len(a)):
			if a[i] % 4 == 0:
				k += d[a[i] % 4] - 1
				continue
			if 4 - a[i] % 4 in d:
				k += d[4 - a[i] % 4]
				if a[i] % 4 == 4 - a[i] % 4:
					k -= 1
		return k // 2