Ishaan has bought N lottery tickets each having an ID denoted by an array A. As a result comes out, Ishaan gets very lucky and gets to know that each one of his tickets has won some prize. But unfortunately, he can't claim all of his lottery tickets.
The "sum_id" of a lottery ticket is the sum of the individual digits of the ticket ID. For example, sum_id of a ticket with ID = 1234 is 1+2+3+4 = 10.
Ishaan can claim the prize of a ticket only if no other ticket with the same sum_id has been claimed by him yet (Refer to example for explanation).
Find out the maximum number of tickets he can claim.
Example 1:
Input:
arr[ ] = {123, 42, 45, 78, 12345}
Output : 3
Explanation:
sum_id of Ticket 1: 1+2+3 = 6 (claimed)
sum_id of Ticket 2: 4+2 = 6 (can't be claimed since Ticket 1, with same sum_id has already been claimed)
sum_id of Ticket 3: 4+5 = 9 (claimed),
sum_id of Ticket 4: 7+8 = 15 (claimed),
sum_id of Ticket 5: 1+2+3+4+5 = 15
(can't be claimed since Ticket 4 with the same sum_id has already been claimed)
Example 2:
Input: 
arr[ ] = {2, 3, 4, 6, 22, 8} 
Output: 5 
 
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 lucky() that takes an array (arr), sizeOfArray (n), and return the maximum number of tickets he can claim. The driver code takes care of the printing.
Expected Time Complexity: O(N).
Expected Auxiliary Space: O(1).
Constraints :
1 ≤ N ≤ 5000
1 ≤ A[i] ≤ 10^{15}

Difficulty: EASY
Tags: Data structures
Skill types: Data structures
Expected Time Complexity: O(N).
Expected Auxiliary Space: O(1).

Starter code:
#User function Template for python3



def lucky (arr, n) : 

    #Complete the function

    



Solutions:
def lucky(arr, n):
	ans = []
	for i in arr:
		x = str(i)
		j = 0
		summ = 0
		while j < len(x):
			summ += int(x[j])
			j += 1
		if summ not in ans:
			ans.append(summ)
	return len(ans)


def lucky(arr, n):
	count = 0
	s = set()
	for i in arr:
		a = str(i)
		b = 0
		for j in a:
			b = b + int(j)
		if b not in s:
			s.add(b)
			count += 1
	return count


def summ(num):
	number = str(num)
	summ = 0
	for i in range(len(number)):
		summ += int(number[i])
	return summ

def lucky(arr, n):
	res = []
	count = 0
	for i in range(n):
		s = summ(arr[i])
		if s > 0 and s not in res:
			count += 1
			res.append(s)
	return count


def lucky(arr, n):
	return len(set([sum(map(int, [*str(item)])) for item in arr]))


def lucky(arr, n):
	dict = {}
	for element in arr:
		value = element
		sum = 0
		while element != 0:
			digit = element % 10
			sum += digit
			element //= 10
		if sum not in dict:
			dict[sum] = True
		sum = 0
	return len(dict)


def lucky(arr, n):
	lis = []
	for i in arr:
		k = str(i)
		s = 0
		for j in k:
			s += int(j)
		if s not in lis:
			lis.append(s)
	return len(lis)


def lucky(arr, n):
	m = {}
	for i in arr:
		s = 0
		d = i
		while d != 0:
			s += d % 10
			d = d // 10
		m[s] = 1
	return len(m)


def lucky(arr, n):
	a1 = []
	for i in range(n):
		res = [int(x) for x in str(arr[i])]
		if sum(res) not in a1:
			a1.append(sum(res))
	return len(a1)


def lucky(arr, n):
	f = 0
	s = set()
	for i in arr:
		s.add(sum([int(j) for j in str(i)]))
	return len(list(s))


def lucky(arr, n):
	dicc = {}
	for i in range(n):
		sum1 = 0
		while arr[i] != 0:
			rem = arr[i] % 10
			sum1 += rem
			arr[i] = arr[i] // 10
		if sum1 in dicc:
			dicc[sum1] += 1
		else:
			dicc[sum1] = 1
	return len(dicc)
for _ in range(0, int(input())):
	n = int(input())
	arr = list(map(int, input().strip().split()))
	ans = lucky(arr, n)
	print(ans)


def lucky(arr, n):
	li = []
	for i in range(n):
		sum2 = 0
		p = arr[i]
		while p != 0:
			a = p % 10
			sum2 += a
			p = p // 10
		li.append(sum2)
	b = list(set(li))
	return len(b)
for _ in range(0, int(input())):
	n = int(input())
	arr = list(map(int, input().strip().split()))
	ans = lucky(arr, n)
	print(ans)


def lucky(arr, n):
	stack = []
	for i in range(n):
		sum1 = 0
		ele = arr[i]
		while ele > 0:
			sum1 = sum1 + ele % 10
			ele = ele // 10
		if sum1 in stack:
			continue
		else:
			stack.append(sum1)
	return len(stack)


def lucky(arr, n):
	list1 = [str(num) for num in arr]
	sum_list = []
	for number in list1:
		sum = 0
		for i in number:
			sum += int(i)
		if sum not in sum_list:
			sum_list.append(sum)
	return len(sum_list)


def lucky(arr, n):
	d = dict()
	c = 0
	for i in arr:
		v = sum([int(j) for j in str(i)])
		if v not in d:
			d[v] = 1
			c += 1
	return c


def lucky(arr, n):
	d = {}
	res = 0
	for n in arr:
		s = 0
		a = n
		while a > 0:
			s += a % 10
			a = a // 10
		if d.get(s, None) is None:
			res += 1
			d[s] = 1
	return res


def digSum(no):
	s = 0
	for i in str(no):
		s += int(i)
	return s

def lucky(arr, n):
	res = list()
	for i in arr:
		if digSum(i) not in res:
			res.append(digSum(i))
	return len(res)


def lucky(arr, n):
	visited = []
	count = 0
	for i in range(n):
		sum_id = 0
		temp = arr[i]
		while temp > 0:
			sum_id += temp % 10
			temp //= 10
		if sum_id not in visited:
			count += 1
			visited.append(sum_id)
	return len(visited)