Ishaan has a craving for sticks. He has N sticks. He observes that some of his sticks are of the same length, and thus he can make squares out of those.
He wants to know how big a square he can make using those sticks as sides. Since the number of sticks is large, he can't do that manually. Can you tell him the maximum area of the biggest square that can be formed?
Also, calculate how many such squares can be made using the sticks.
 
Example 1:
Ã¢â¬â¹Input : arr[ ] = {2, 2, 2, 9, 2, 2, 2, 2, 2}
Output : 4 2
Explanation:
2 squares of side 2 are formed.
return maximum area and number of square.
Ã¢â¬â¹Example 2:
Input : arr[ ] = {5, 3, 2, 3, 6, 3, 3} 
Output :  9 1
 
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 square() that takes an array (arr), sizeOfArray (n) and return the array of the maximum area of the largest square that can be formed and the number of squares that can be formed if there is no possible square return -1. The driver code takes care of the printing.
Expected Time Complexity: O(N).
Expected Auxiliary Space: O(M), where M is the maximum value of an array.
 
Constraints : 
1 ≤ N ≤ 10^{5}
1 ≤ arr_{i} ≤ 10^{3}

Source: geeksforgeeks | Difficulty: EASY
Tags: String algorithms

Sorting

Data structures

Starter code: #User function Template for python3



def square (arr, n) : 

    #Complete the function

    



Solutions:
def square(arr, n):
	d = {}
	square = 1
	area = {}
	res = [0, 0]
	for elem in arr:
		d.update({elem: d.get(elem, 0) + 1})
		if d[elem] % 4 == 0:
			value = elem * elem
			area.update({value: area.get(value, 0) + 1})
			if value >= res[0]:
				res = [value, area[value]]
	return res if res[0] else [-1]


def square(arr, n):
	d = {}
	for i in arr:
		if i not in d:
			d[i] = 1
		else:
			d[i] += 1
	b = []
	for i in d:
		if d[i] // 4 > 0:
			b.append([i * i, d[i] // 4])
	if b:
		b.sort()
		return b[-1]
	return [-1]


def square(arr, n):
	(area, cnt) = (0, 0)
	rec = Counter(arr)
	for (k, v) in rec.items():
		if v >= 4:
			if k * k > area:
				area = k * k
				cnt = v // 4
	if area == 0:
		return [-1]
	return (area, cnt)
from collections import Counter


def square(arr, n):
	d = {}
	for i in arr:
		if i in d:
			d[i] += 1
		else:
			d[i] = 1
	mx = 0
	cx = 0
	for i in d:
		if d[i] >= 4:
			t = d[i] // 4
			j = i ** 2
			if j > mx:
				mx = j
				cx = t
	if mx == 0:
		return [-1]
	return [mx, cx]


def square(arr, n):
	d = {}
	for i in arr:
		if i in d:
			d[i] += 1
		else:
			d[i] = 1
	a = 0
	sq = 0
	res = []
	for (i, j) in d.items():
		if j >= 4:
			area = i * i
			if area > a:
				a = area
				sq = int(j / 4)
	if a > 0:
		res.append(a)
		res.append(sq)
	else:
		res.append(-1)
	return res


def square(arr, n):
	d1 = {}
	li = []
	for i in arr:
		d1[i] = d1.get(i, 0) + 1
	for i in d1:
		if d1.get(i) >= 4:
			li.append(i)
	if len(li) == 0:
		return [-1]
	li.sort()
	return [li[-1] * li[-1], d1.get(li[-1]) // 4]


def square(arr, n):
	dict = {}
	result = []
	for element in arr:
		dict[element] = dict.get(element, 0) + 1
	for key in dict:
		if dict[key] >= 4:
			result.append(key * key)
			result.append(dict[key] // 4)
	if len(result) > 0:
		return result[len(result) - 2:]
	else:
		return [-1]


from collections import Counter

def square(arr, n):
	c = Counter(arr)
	result = [-1]
	for item in c:
		if c[item] // 4:
			size = item * item
			num = c[item] // 4
			if size > result[0]:
				result = [size, num]
	return result


def square(arr, n):
	freq = {}
	for i in range(n):
		if arr[i] not in freq:
			freq[arr[i]] = 1
		else:
			freq[arr[i]] += 1
	ma = 0
	mi = 0
	it = list(freq.items())
	for i in range(len(it)):
		if it[i][1] >= 4 and it[i][0] > ma:
			ma = it[i][0]
			mi = it[i][1]
	if ma == 0:
		return (-1,)
	return (ma * ma, mi // 4)


from collections import Counter

def square(arr, n):
	c = Counter(arr)
	flag = -1
	for i in sorted(c.keys()):
		if c[i] >= 4:
			flag = i
	return [flag ** 2, c[flag] // 4] if flag != -1 else [-1]


def square(arr, n):
	d = {}
	side = 0
	max_square = 1
	for i in range(n):
		if arr[i] not in d:
			d[arr[i]] = 1
		else:
			d[arr[i]] += 1
	for (k, v) in d.items():
		if k > side and v // 4 >= 1:
			max_square = v // 4
			side = k
	if side == 0 or max_square == 0:
		return (-1,)
	return (side ** 2, max_square)


def square(arr, n):
	arr.sort()
	i = 0
	ma = -99999999
	co = 0
	m = 0
	t = arr[0]
	while i < n:
		if arr[i] != t:
			c = m // 4
			if c >= 1:
				if ma < arr[i - 1] ** 2:
					ma = arr[i - 1] ** 2
					co = c
			t = arr[i]
			m = 0
		m += 1
		i += 1
	c = m // 4
	if c >= 1:
		if ma < arr[-1] ** 2:
			ma = arr[-1] ** 2
			co = c
	return (ma, co) if co > 0 else (-1,)
for _ in range(0, int(input())):
	n = int(input())
	arr = list(map(int, input().strip().split()))
	ans = square(arr, n)
	print(*ans)


def square(arr, n):
	d = {}
	l = []
	for i in arr:
		if i in d:
			d[i] += 1
		else:
			d[i] = 1
	for (i, j) in enumerate(arr):
		if d[j] >= 4:
			l.append(j)
	if len(l) > 0:
		return (max(l) ** 2, d[max(l)] // 4)
	return (-1,)
for _ in range(0, int(input())):
	n = int(input())
	arr = list(map(int, input().strip().split()))
	ans = square(arr, n)
	print(*ans)


from collections import Counter as C

def square(arr, n):
	z = 0
	for (i, j) in C(arr).items():
		if j > 3:
			z = max(z, i)
	d = C(arr)
	return [z * z, d[z] // 4] if z else [-1]


from collections import defaultdict

def square(arr, n):
	d = defaultdict(int)
	for i in arr:
		d[i] += 1
	l = sorted(d.items(), key=lambda x: x[0], reverse=True)
	area = 0
	count = 0
	for tup in l:
		if tup[1] >= 4:
			area = tup[0] * tup[0]
			count = tup[1] // 4
			break
	if area == 0 or count == 0:
		return [-1]
	return [area, count]


def square(arr, n):
	d = {}
	for i in arr:
		if i in d:
			d[i] += 1
		else:
			d[i] = 1
	b = 0
	for i in d:
		if i > b and d[i] >= 4:
			b = i
	if b == 0:
		return [-1]
	else:
		return (b * b, arr.count(b) // 4)


def square(arr, n):
	dict_ = {}
	for i in range(n):
		if arr[i] not in dict_:
			dict_[arr[i]] = 1
		else:
			dict_[arr[i]] += 1
	MAX = 0
	side = 0
	for (key, val) in dict_.items():
		if val >= 4:
			if MAX < key * key:
				MAX = key * key
				side = val // 4
	res = []
	if MAX == 0:
		res.append(-1)
	else:
		res.append(MAX)
		res.append(side)
	return res
	return res


from collections import defaultdict

def square(arr, n):
	d = defaultdict(lambda : 0)
	for i in range(n):
		d[arr[i]] += 1
	c = 0
	l = []
	for i in d.keys():
		if d[i] >= 4:
			g = i * i
			c += 1
			h = d[i] // 4
	if c == 0:
		return [-1]
	else:
		l.append(g)
		l.append(h)
		return l


from collections import defaultdict

def square(arr, n):
	ans = -1
	num = -1
	d = defaultdict(lambda : 0)
	for i in arr:
		d[i] += 1
	for i in d:
		k = d[i] // 4
		if k != 0:
			if i * i > ans:
				ans = i * i
				num = k
	if ans == -1:
		l = [-1]
		return l
	l = [ans, num]
	return l


def square(arr, n):
	dic = {}
	for i in arr:
		dic[i] = dic.get(i, 0) + 1
	mx = -1
	no = 0
	for i in dic:
		if dic[i] >= 4:
			if i * i > mx:
				mx = i * i
				no = dic[i] // 4
	if mx == -1:
		return [-1]
	return [mx, no]


from collections import Counter

def square(arr, n):
	c = Counter(arr)
	countSquares = maxSideLength = 0
	for sideLength in c:
		if c[sideLength] >= 4:
			maxSideLength = max(maxSideLength, sideLength)
			countSquares = c[sideLength] // 4
	if countSquares == 0:
		return [-1]
	return [maxSideLength * maxSideLength, countSquares]


def square(arr, n):
	mapp = {}
	(size, maxi) = (0, 0)
	sq_area = 0
	for ele in arr:
		if ele not in mapp:
			mapp[ele] = 1
		else:
			mapp[ele] += 1
	for ele in mapp:
		val = mapp[ele]
		if val >= 4:
			sq_area = ele ** 2
		if sq_area > maxi:
			maxi = sq_area
			size = val // 4
	if size == 0:
		return [-1]
	return (maxi, size)


from collections import Counter

def square(arr, n):
	d = Counter(arr)
	area = 0
	res = 0
	for i in d:
		if d[i] >= 4:
			res = 0
			res = res + d[i] // 4
			k = i * i
			if k > area:
				area = k
	if area == res == 0:
		return [-1]
	return (area, res)


def square(arr, n):
	dictt = {}
	for ele in arr:
		dictt[ele] = dictt.get(ele, 0) + 1
	(maxi, sq_size) = (0, 0)
	area = 0
	for (x, y) in dictt.items():
		if y >= 4:
			area = x ** 2
		if area > maxi:
			maxi = area
			sq_size = y // 4
	if sq_size == 0:
		return [-1]
	return [maxi, sq_size]


def square(arr, n):
	m = dict()
	a = 0
	for i in range(n):
		m[arr[i]] = m.get(arr[i], 0) + 1
	max = 0
	for j in m:
		if m[j] >= 4 and j > a:
			a = j
			max = m[j]
	if a == 0:
		return [-1]
	return [a * a, max // 4]


def square(arr, n):
	d = {}
	for i in arr:
		if i not in d:
			d[i] = 1
		else:
			d[i] += 1
	area = 0
	sq = 0
	for i in d:
		if d[i] >= 4:
			area = max(i * i, area)
			sq = d[i] // 4
	ans = []
	if area == 0:
		ans.append(-1)
	else:
		ans.append(area)
		ans.append(sq)
	return ans


def square(arr, n):
	d = dict()
	for i in arr:
		if i in d:
			d[i] += 1
		else:
			d[i] = 1
	mx_area = 0
	area = 0
	sq_count = 0
	for (i, j) in d.items():
		if j >= 4:
			area = i ** 2
		if area > mx_area:
			mx_area = area
			sq_count = j // 4
	if sq_count == 0:
		return [-1]
	return (mx_area, sq_count)


from collections import Counter

def square(arr, n):
	result = []
	if n < 4:
		return [-1]
	count = Counter(arr)
	c = 0
	a = 0
	for k in count.keys():
		if count[k] // 4 > 0 and k * k > a:
			c = count[k] // 4
			a = k * k
	if c == 0:
		return [-1]
	return [a, c]


def square(arr, n):
	d = {}
	f = {}
	l = []
	for item in arr:
		if d.get(item) == None:
			d[item] = 1
		else:
			d[item] = d[item] + 1
			if d.get(item) % 4 == 0:
				p = pow(item, 2)
				if p not in f:
					f[p] = 1
				else:
					f[p] = f[p] + 1
				l.append((p, f[p]))
	if len(l) == 0:
		return [-1]
	return list(max(l))


def square(arr, n):
	dic1 = {}
	for i in range(n):
		if arr[i] in dic1:
			dic1[arr[i]] += 1
		else:
			dic1[arr[i]] = 1
	max1 = -1
	maxno = -1
	for i in dic1:
		if dic1[i] >= 4:
			area = i * i
			no = dic1[i] // 4
			if max1 < area:
				max1 = area
				maxno = no
	if max1 == -1:
		return (-1,)
	return (max1, maxno)