Given an array of positive integers of size N, form groups of two or three such that the sum of all elements in a group is a multiple of 3. Count all possible number of groups that can be generated in this way. 
Example 1:
Input:
N = 5
arr[] = {3, 6, 7, 2, 9}
Output: 8
Explanation: 
Groups of two are: 
{3, 6}, {3, 9}, {9, 6}, {7, 2}.
Groups of three are: 
{3, 7, 2}, {7, 2, 6}, {7, 2, 9}, {3, 6, 9}.
Example 2:
Input:
N = 4
arr[] = {2, 1, 3, 4}
Output: 4
Explanation: Groups are {2,1}, {2,4}, 
{2,1,3}, {2,4,3}
Your Task:
You don't need to read input or print anything. Your task is to complete the function findgroups() which takes arr[] and n as input parameters and returns the number of possible groups.
Expected Time Complexity: O(N)
Expected Auxiliary Space: O(1)
Constraints:
1 ≤ N ≤ 10^{6}
1 ≤ arr_{i} ≤ 10^{6}

Source: geeksforgeeks | Difficulty: MEDIUM
Tags: Data structures

Starter code: #User function Template for python3

class Solution:
    def findgroups(self, arr, n):
        # code here

Solutions:
class Solution:

	def findgroups(self, arr, n):
		c = [0, 0, 0]
		res = 0
		for el in arr:
			c[el % 3] += 1
		res += c[0] * (c[0] - 1) / 2
		res += c[1] * c[2]
		res += c[0] * (c[0] - 1) * (c[0] - 2) / 6
		res += c[1] * (c[1] - 1) * (c[1] - 2) / 6
		res += c[2] * (c[2] - 1) * (c[2] - 2) / 6
		res += c[0] * c[1] * c[2]
		return int(res)


from collections import defaultdict

class Solution:

	def findgroups(self, arr, n):
		d = defaultdict(int)
		for a in arr:
			d[a % 3] += 1
		ans = d[1] * d[2] + d[0] * (d[0] - 1) // 2
		ans += d[0] * d[1] * d[2]
		ans += d[0] * (d[0] - 1) * (d[0] - 2) // 6
		ans += d[1] * (d[1] - 1) * (d[1] - 2) // 6
		ans += d[2] * (d[2] - 1) * (d[2] - 2) // 6
		return ans


class Solution:

	def findgroups(self, arr, n):
		freq = [0] * 3
		for i in arr:
			freq[i % 3] += 1
		c = 0
		c += max(freq[0] * (freq[0] - 1), 0) // 2
		c += freq[1] * freq[2]
		c += max(freq[0] * (freq[0] - 1) * (freq[0] - 2), 0) // 6
		c += freq[0] * freq[1] * freq[2]
		c += max(freq[1] * (freq[1] - 1) * (freq[1] - 2), 0) // 6
		c += max(freq[2] * (freq[2] - 1) * (freq[2] - 2), 0) // 6
		return c


class Solution:

	def findgroups(self, a, n):
		cnt0 = 0
		cnt1 = 0
		cnt2 = 0
		for i in range(n):
			if a[i] % 3 == 0:
				cnt0 += 1
			elif a[i] % 3 == 1:
				cnt1 += 1
			else:
				cnt2 += 1
		ans = cnt0 * (cnt0 - 1) // 2 + cnt1 * cnt2 + cnt0 * (cnt0 - 1) * (cnt0 - 2) // 6 + cnt0 * cnt1 * cnt2 + cnt1 * (cnt1 - 1) * (cnt1 - 2) // 6 + cnt2 * (cnt2 - 1) * (cnt2 - 2) // 6
		return ans


from collections import Counter
from math import factorial

class Solution:

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


class Solution:

	def findgroups(self, arr, n):
		a0 = 0
		a1 = 0
		a2 = 0
		for i in range(n):
			if arr[i] % 3 == 0:
				a0 = a0 + 1
			elif arr[i] % 3 == 1:
				a1 = a1 + 1
			else:
				a2 = a2 + 1
		ans = 0
		if a0 > 1:
			ans = ans + a0 * (a0 - 1) // 2
		if a0 > 2:
			ans += a0 * (a0 - 1) * (a0 - 2) // 6
		if a1 > 2:
			ans += a1 * (a1 - 1) * (a1 - 2) // 6
		if min(a1, a2) >= 1:
			x = a1 * a2
			ans = ans + x
			ans = ans + x * a0
		if a2 > 2:
			ans = ans + a2 * (a2 - 1) * (a2 - 2) // 6
		return ans


class Solution:

	def findgroups(self, arr, n):
		if not arr:
			return
		c = [0, 0, 0]
		res = 0
		for i in range(0, n):
			c[arr[i] % 3] += 1
		res += c[0] * (c[0] - 1) // 2
		res += c[1] * c[2]
		res += c[0] * (c[0] - 1) * (c[0] - 2) // 6
		res += c[1] * (c[1] - 1) * (c[1] - 2) // 6
		res += c[2] * (c[2] - 1) * (c[2] - 2) // 6
		res += c[0] * c[1] * c[2]
		return res


class Solution:

	def findgroups(self, lst, n):
		res = 0
		arr = [0] * 3
		for i in range(n):
			arr[lst[i] % 3] += 1
		res += arr[0] * (arr[0] - 1) // 2
		res += arr[1] * arr[2]
		res += arr[0] * arr[1] * arr[2]
		res += arr[0] * (arr[0] - 1) * (arr[0] - 2) // 6
		res += arr[1] * (arr[1] - 1) * (arr[1] - 2) // 6
		res += arr[2] * (arr[2] - 1) * (arr[2] - 2) // 6
		return res


class Solution:

	def findgroups(self, arr, n):
		rem = [0, 0, 0]
		for i in arr:
			rem[i % 3] += 1
		count = 0
		count += rem[0] * (rem[0] - 1) // 2
		count += rem[1] * rem[2]
		count += rem[0] * (rem[0] - 1) * (rem[0] - 2) // 6
		count += rem[1] * (rem[1] - 1) * (rem[1] - 2) // 6
		count += rem[2] * (rem[2] - 1) * (rem[2] - 2) // 6
		count += rem[0] * rem[1] * rem[2]
		return count


from collections import Counter

class Solution:

	def findgroups(self, arr, n):
		d = Counter([i % 3 for i in arr])
		return d[0] * (d[0] - 1) // 2 + d[1] * d[2] + d[0] * (d[0] - 1) * (d[0] - 2) // 6 + d[1] * (d[1] - 1) * (d[1] - 2) // 6 + d[2] * (d[2] - 1) * (d[2] - 2) // 6 + d[0] * d[1] * d[2]


class Solution:

	def findgroups(self, arr, n):
		a = 0
		b = 0
		c = 0
		for x in arr:
			if x % 3 == 0:
				a += 1
			if x % 3 == 1:
				b += 1
			if x % 3 == 2:
				c += 1
		return int(a * (a - 1) / 2 + a * (a - 1) * (a - 2) / 6 + a * b * c + b * (b - 1) * (b - 2) / 6 + b * c + c * (c - 1) * (c - 2) / 6)


class Solution:

	def findgroups(self, arr, n):
		d = {0: [], 1: [], 2: []}
		for i in arr:
			d[i % 3].append(i)
		count = 0
		p = len(d[0])
		count += p * (p - 1) / 2
		(n, m) = (len(d[1]), len(d[2]))
		count += n * m
		count += p * (p - 1) * (p - 2) / 6
		count += n * (n - 1) * (n - 2) / 6
		count += m * (m - 1) * (m - 2) / 6
		count += n * m * p
		return int(count)


import math

class Solution:

	def findgroups(self, arr, n):

		def fact(t):
			return math.factorial(t)
		a = [0, 0, 0]
		for i in arr:
			a[i % 3] += 1
		tot = 0
		if a[0] >= 2:
			tot += fact(a[0]) / (fact(2) * fact(a[0] - 2))
		if a[0] >= 3:
			tot += fact(a[0]) / (fact(3) * fact(a[0] - 3))
		if a[1] >= 3:
			tot += fact(a[1]) / (fact(3) * fact(a[1] - 3))
		if a[2] >= 3:
			tot += fact(a[2]) / (fact(3) * fact(a[2] - 3))
		g = 0
		if a[1] >= 1 and a[2] >= 1:
			g = a[1] * a[2]
			tot += g
		tot += g * a[0]
		return int(tot)


class Solution:

	def findgroups(self, arr, n):
		dict_a = {}
		s = 0
		for i in range(n):
			if arr[i] % 3 in dict_a:
				dict_a[arr[i] % 3] += 1
			else:
				dict_a[arr[i] % 3] = 1
		if 0 not in dict_a:
			dict_a[0] = 0
		if 1 not in dict_a:
			dict_a[1] = 0
		if 2 not in dict_a:
			dict_a[2] = 0
		s += dict_a[0] * (dict_a[0] - 1) / 2
		s += dict_a[1] * dict_a[2]
		s += dict_a[0] * dict_a[1] * dict_a[2]
		s += dict_a[0] * (dict_a[0] - 1) * (dict_a[0] - 2) / 6
		s += dict_a[1] * (dict_a[1] - 1) * (dict_a[1] - 2) / 6
		s += dict_a[2] * (dict_a[2] - 1) * (dict_a[2] - 2) / 6
		return int(s)


class Solution:

	def findgroups(self, arr, n):
		a = b = c = 0
		for i in arr:
			if i % 3 == 0:
				a += 1
			elif i % 3 == 1:
				b += 1
			else:
				c += 1
		ans = 0
		ans += b * c
		if a >= 2:
			ans += a * (a - 1) // 2
		if a >= 3:
			ans += a * (a - 1) * (a - 2) // 6
		ans += a * b * c
		if b >= 3:
			ans += b * (b - 1) * (b - 2) // 6
		if c >= 3:
			ans += c * (c - 1) * (c - 2) // 6
		return ans


class Solution:

	def findgroups(self, arr, n):
		r0 = r1 = r2 = 0
		for i in range(n):
			if arr[i] % 3 == 0:
				r0 += 1
			elif arr[i] % 3 == 1:
				r1 += 1
			else:
				r2 += 1
		two = r0 * (r0 - 1) // 2 + r1 * r2
		three = r0 * (r0 - 1) * (r0 - 2) // 6 + r0 * r1 * r2 + r1 * (r1 - 1) * (r1 - 2) // 6 + r2 * (r2 - 1) * (r2 - 2) // 6
		return two + three
if __name__ == '__main__':
	tc = int(input())
	while tc > 0:
		n = int(input())
		arr = list(map(int, input().strip().split()))
		ob = Solution()
		ans = ob.findgroups(arr, n)
		print(ans)
		tc -= 1


class Solution:

	def findgroups(self, arr, n):
		mod = [0, 0, 0]
		tot = 0
		for x in arr:
			if x % 3 == 0:
				mod[0] += 1
			elif x % 3 == 1:
				mod[1] += 1
			else:
				mod[2] += 1
		tot += mod[0] * (mod[0] - 1) / 2
		tot += mod[1] * mod[2]
		tot += mod[0] * (mod[0] - 1) * (mod[0] - 2) / 6
		tot += mod[1] * (mod[1] - 1) * (mod[1] - 2) / 6
		tot += mod[2] * (mod[2] - 1) * (mod[2] - 2) / 6
		tot += mod[0] * mod[1] * mod[2]
		return int(tot)
if __name__ == '__main__':
	tc = int(input())
	while tc > 0:
		n = int(input())
		arr = list(map(int, input().strip().split()))
		ob = Solution()
		ans = ob.findgroups(arr, n)
		print(ans)
		tc -= 1


from collections import Counter

class Solution:

	def findgroups(self, arr, n):
		arr = [x % 3 for x in arr]
		cnt = Counter(arr)
		ans = 0
		ans += cnt[0] * (cnt[0] - 1) // 2
		ans += cnt[1] * cnt[2]

		def f(x):
			return x * (x - 1) * (x - 2) // 6
		ans += f(cnt[0])
		ans += f(cnt[1])
		ans += f(cnt[2])
		ans += cnt[0] * cnt[1] * cnt[2]
		return ans
if __name__ == '__main__':
	tc = int(input())
	while tc > 0:
		n = int(input())
		arr = list(map(int, input().strip().split()))
		ob = Solution()
		ans = ob.findgroups(arr, n)
		print(ans)
		tc -= 1


class Solution:

	def findgroups(self, arr, n):
		numGrps = 0
		count = {0: 0, 1: 0, 2: 0}
		for ele in arr:
			remainder = ele % 3
			count[remainder] += 1
		numGrps += count[0] * (count[0] - 1) / 2
		numGrps += count[1] * count[2]
		numGrps += count[0] * (count[0] - 1) * (count[0] - 2) / 6
		numGrps += count[1] * (count[1] - 1) * (count[1] - 2) / 6
		numGrps += count[2] * (count[2] - 1) * (count[2] - 2) / 6
		numGrps += count[0] * count[1] * count[2]
		return int(numGrps)


class Solution:

	def findgroups(self, a, n):
		rem = [0] * 3
		count = 0
		for x in a:
			rem[x % 3] += 1
		count += rem[0] * (rem[0] - 1) / 2
		count += rem[1] * rem[2]
		count += rem[0] * (rem[0] - 1) * (rem[0] - 2) / 6
		count += rem[0] * rem[1] * rem[2]
		count += rem[1] * (rem[1] - 1) * (rem[1] - 2) / 6
		count += rem[2] * (rem[2] - 1) * (rem[2] - 2) / 6
		return int(count)


class Solution:

	def findgroups(self, arr, n):
		c = [0] * 3
		count = 0
		for i in range(len(arr)):
			c[arr[i] % 3] += 1
		count += c[0] * (c[0] - 1) // 2
		count += c[1] * c[2]
		count += c[0] * (c[0] - 1) * (c[0] - 2) // 6
		count += c[1] * (c[1] - 1) * (c[1] - 2) // 6
		count += c[2] * (c[2] - 1) * (c[2] - 2) // 6
		count += c[0] * c[1] * c[2]
		return count


class Solution:

	def findgroups(self, arr, n):
		l = [0, 0, 0]
		res = 0
		for i in range(len(arr)):
			if arr[i] % 3 == 2:
				arr[i] = -1
			else:
				arr[i] = arr[i] % 3
		for i in arr:
			l[i + 1] += 1
		if l[1] > 0:
			res += l[1] * (l[1] - 1) // 2
		res += l[0] * l[2]
		res += l[0] * (l[0] - 1) * (l[0] - 2) // 6
		res += l[1] * (l[1] - 1) * (l[1] - 2) // 6
		res += l[2] * (l[2] - 1) * (l[2] - 2) // 6
		res += l[0] * l[1] * l[2]
		return res


class Solution:

	def findgroups(self, arr, n):
		rem0 = 0
		rem1 = 0
		rem2 = 0
		total = 0
		for i in arr:
			if i % 3 == 0:
				rem0 += 1
			if i % 3 == 1:
				rem1 += 1
			if i % 3 == 2:
				rem2 += 1
		total += int((rem0 - 1) * rem0 / 2)
		total += int(rem1 * rem2)
		thpr = rem0 - 2
		while thpr > 0:
			total += int(thpr * (thpr + 1) / 2)
			thpr -= 1
		thpr = rem1 - 2
		while thpr > 0:
			total += int(thpr * (thpr + 1) / 2)
			thpr -= 1
		thpr = rem2 - 2
		while thpr > 0:
			total += int(thpr * (thpr + 1) / 2)
			thpr -= 1
		total += int(rem1 * rem2 * rem0)
		return total


class Solution:

	def findgroups(self, arr, n):
		mod = [0, 0, 0]
		for i in arr:
			mod[i % 3] += 1
		result = 0
		result += mod[0] * (mod[0] - 1) // 2
		result += mod[1] * mod[2]
		if mod[0] > 2:
			result += mod[0] * (mod[0] - 1) * (mod[0] - 2) // 6
		if mod[1] > 2:
			result += mod[1] * (mod[1] - 1) * (mod[1] - 2) // 6
		if mod[2] > 2:
			result += mod[2] * (mod[2] - 1) * (mod[2] - 2) // 6
		result += mod[0] * mod[1] * mod[2]
		return result


import math

def ncr(n, r, dp):
	if n < r:
		return 0
	if n == r:
		return 1
	return math.factorial(n) // (math.factorial(n - r) * math.factorial(r))
dp = []

class Solution:

	def findgroups(self, arr, n):
		temp = [i % 3 for i in arr]
		cnt = [0, 0, 0]
		for i in temp:
			cnt[i] += 1
		ans = 0
		ans += ncr(cnt[0], 2, dp)
		ans += cnt[2] * cnt[1]
		ans += ncr(cnt[0], 3, dp)
		ans += ncr(cnt[1], 3, dp)
		ans += ncr(cnt[2], 3, dp)
		ans += cnt[0] * cnt[1] * cnt[2]
		return ans


import math

class Solution:

	def findgroups(self, arr, n):
		mod_groups = {1: 0, 2: 0, 0: 0}
		for i in arr:
			mod_groups[i % 3] += 1
		sol = self.nChooseK(mod_groups[0], 2) + self.nChooseK(mod_groups[0], 3)
		sol += self.nChooseK(mod_groups[2], 3)
		sol += self.nChooseK(mod_groups[1], 3)
		sol += mod_groups[1] * mod_groups[2]
		sol += mod_groups[1] * mod_groups[2] * mod_groups[0]
		return sol

	def nChooseK(self, n, k):
		nFaculty = math.factorial(n)
		kFaculty = math.factorial(k)
		if n - k < 0:
			return 0
		nMinKFaculty = math.factorial(n - k)
		return nFaculty // (kFaculty * nMinKFaculty)


class Solution:

	def findgroups(self, arr, n):
		count_0 = 0
		count_1 = 0
		count_2 = 0
		for i in range(len(arr)):
			if arr[i] % 3 == 0:
				count_0 += 1
			elif arr[i] % 3 == 1:
				count_1 += 1
			elif arr[i] % 3 == 2:
				count_2 += 1
		group_12_2 = count_1 * count_2
		group_3_2 = count_0 * (count_0 - 1) // 2
		group_3_3 = count_0 * (count_0 - 1) * (count_0 - 2) // 6
		group_1_3 = count_1 * (count_1 - 1) * (count_1 - 2) // 6
		group_2_3 = count_2 * (count_2 - 1) * (count_2 - 2) // 6
		group_0_1_2_3 = count_0 * group_12_2
		return group_12_2 + group_3_2 + group_3_3 + group_1_3 + group_2_3 + group_0_1_2_3


class Solution:

	def findgroups(self, arr, n):
		cnts = [0] * 3
		for x in arr:
			cnts[x % 3] += 1
		ans = cnts[0] * (cnts[0] - 1) // 2 + cnts[1] * cnts[2] + cnts[0] * cnts[1] * cnts[2]
		ans += sum([cnts[x] * (cnts[x] - 1) * (cnts[x] - 2) // 6 for x in [1, 2, 0]])
		return ans


class Solution:

	def findgroups(self, arr, n):
		count = 0
		h = [0] * 3
		for i in range(n):
			h[arr[i] % 3] += 1
		count += h[1] * h[2]
		count += h[0] * (h[0] - 1) // 2
		count += h[0] * h[1] * h[2]
		count += h[0] * (h[0] - 1) * (h[0] - 2) / 6
		count += h[1] * (h[1] - 1) * (h[1] - 2) / 6
		count += h[2] * (h[2] - 1) * (h[2] - 2) / 6
		return int(count)


import math

class Solution:

	def findgroups(self, arr, n):
		(r1, r2, r3) = (0, 0, 0)
		for i in arr:
			if i % 3 == 1:
				r2 = r2 + 1
			if i % 3 == 2:
				r3 = r3 + 1
			if i % 3 == 0:
				r1 = r1 + 1
		count = 0
		(c1, c2, c3) = (0, 0, 0)
		if r1 >= 3:
			c1 = math.factorial(r1) // (6 * math.factorial(max(0, r1 - 3)))
		if r2 >= 3:
			c2 = math.factorial(r2) // (6 * math.factorial(max(0, r2 - 3)))
		if r3 >= 3:
			c3 = math.factorial(r3) // (6 * math.factorial(max(0, r3 - 3)))
		c4 = r1 * r2 * r3
		c5 = r3 * r2
		c6 = r1 * (r1 - 1) // 2
		count = count + c1 + c2 + c3 + c4 + c5 + c6
		return count


class Solution:

	def nC2(self, n):
		return n * (n - 1) // 2

	def nC3(self, n):
		return n * (n - 1) * (n - 2) // 6

	def findgroups(self, arr, n):
		arr = [x % 3 for x in arr]
		counts = {0: 0, 1: 0, 2: 0}
		for num in arr:
			counts[num] += 1
		res = self.nC2(counts[0])
		res += counts[1] * counts[2]
		res += self.nC3(counts[0])
		res += self.nC3(counts[1])
		res += self.nC3(counts[2])
		res += counts[0] * counts[1] * counts[2]
		return res