Given an unsorted array Arr of size N of positive integers. One number 'A' from set {1, 2,....,N} is missing and one number 'B' occurs twice in array. Find these two numbers.
Example 1:
Input:
N = 2
Arr[] = {2, 2}
Output: 2 1
Explanation: Repeating number is 2 and 
smallest positive missing number is 1.
Example 2:
Input:
N = 3
Arr[] = {1, 3, 3}
Output: 3 2
Explanation: Repeating number is 3 and 
smallest positive missing number is 2.
Your Task:
You don't need to read input or print anything. Your task is to complete the function findTwoElement() which takes the array of integers arr and n as parameters and returns an array of integers of size 2 denoting the answer ( The first index contains B and second index contains A.)
Expected Time Complexity: O(N)
Expected Auxiliary Space: O(1)
Constraints:
2 ≤ N ≤ 10^{5}
1 ≤ Arr[i] ≤ N

Source: geeksforgeeks | Difficulty: MEDIUM
Tags: Data structures

Starter code: #User function Template for python3



class Solution:

    def findTwoElement( self,arr, n): 

        # code here

Solutions:
class Solution:

	def findTwoElement(self, arr, n):
		unordered_map = {}
		rep = 0
		miss = 0
		for i in arr:
			if i not in unordered_map:
				unordered_map[i] = 1
			else:
				rep = i
		for i in range(1, n + 1):
			if i not in unordered_map:
				miss = i
				return [rep, miss]


class Solution:

	def findTwoElement(self, arr, n):
		sei = [False] * n
		for i in arr:
			if sei[i - 1]:
				repeated = i
			else:
				sei[i - 1] = True
		for i in range(n):
			if not sei[i]:
				return [repeated, i + 1]


class Solution:

	def findTwoElement(self, arr, n):
		d = {}
		b = 0
		for i in arr:
			try:
				d[i] += 1
				r = i
			except:
				d[i] = 1
		f = False
		for i in range(1, max(arr)):
			if i not in d:
				l = i
				f = True
				break
		if f == False:
			return (r, max(arr) + 1)
		return (r, l)


class Solution:

	def findTwoElement(self, arr, n):
		a = list(range(1, len(arr) + 1))
		res = sum(a)
		tot = sum(arr)
		arr = set(arr)
		sum_arr = sum(arr)
		missing = res - sum_arr
		repeated = tot - sum_arr
		return (repeated, missing)


class Solution:

	def findTwoElement(self, arr, n):
		l = []
		s1 = sum(arr)
		k = set(arr)
		k = list(k)
		s2 = sum(k)
		l.append(s1 - s2)
		s3 = n * (n + 1) // 2
		l.append(s3 - s2)
		return l


from collections import Counter

class Solution:

	def findTwoElement(self, arr, n):
		a = set(range(1, n + 1))
		missing = list(a - set(arr))[0]
		dic = {}
		for i in arr:
			if i not in dic:
				dic[i] = 1
			else:
				dic[i] += 1
			if dic[i] > 1:
				return [i, missing]


class Solution:

	def findTwoElement(self, arr, n):
		m = max(arr)
		b = [i for i in range(1, n + 1)]
		s = list(set(b) - set(arr))
		dic = {}
		for i in arr:
			if i in dic:
				s.insert(0, i)
				return s
			else:
				dic[i] = 1


class Solution:

	def findTwoElement(self, arr, n):
		A = set(range(1, n + 1))
		missing = list(A - set(arr))[0]
		dic = {}
		for i in arr:
			if i not in dic:
				dic[i] = 0
			dic[i] += 1
			if dic[i] >= 2:
				return [i, missing]


class Solution:

	def findTwoElement(self, arr, n):
		(a, b) = (0, 0)
		for i in range(n):
			if arr[abs(arr[i]) - 1] < 0:
				a = abs(arr[i])
			else:
				arr[abs(arr[i]) - 1] = -arr[abs(arr[i]) - 1]
		for i in range(n):
			if arr[i] > 0:
				b = i + 1
				break
		return (a, b)


class Solution:

	def findTwoElement(self, arr, n):
		arr.sort()
		missing = None
		r = None
		for i in range(n - 1):
			if arr[i] == arr[i + 1]:
				r = arr[i]
				arr.remove(r)
				break
		for i in range(1, n):
			if i != arr[i - 1]:
				missing = i
				break
		if not missing:
			missing = arr[n - 2] + 1
		return [r, missing]


class Solution:

	def findTwoElement(self, arr, n):
		temp = [0] * (n + 1)
		ans = []
		for i in range(n):
			temp[arr[i]] += 1
		for i in range(1, n + 1):
			if temp[i] > 1:
				ans.insert(0, i)
			if temp[i] == 0:
				ans.insert(1, i)
		return ans


class Solution:

	def findTwoElement(self, arr, size):
		for i in arr:
			if arr[abs(i) - 1] > 0:
				arr[abs(i) - 1] = -arr[abs(i) - 1]
			else:
				rep = abs(i)
		for i in range(len(arr)):
			if arr[i] > 0:
				nonRep = i + 1
		return (rep, nonRep)


class Solution:

	def findTwoElement(self, arr, n):
		dict = {}
		for i in arr:
			if i not in dict:
				dict[i] = 1
			else:
				a = i
				dict[i] += 1
				break
		s = sum(arr) - a
		s1 = n * (n + 1) // 2 - s
		return [a, s1]


class Solution:

	def findTwoElement(self, arr, n):
		total_sum = n * (n + 1) // 2
		s1 = sum(set(arr))
		s2 = sum(arr)
		s = s2 - s1
		k = total_sum - s1
		return (s, k)


class Solution:

	def findTwoElement(self, arr, n):
		missing = -1
		repeat = -1
		mp = [0] * (n + 1)
		for i in range(n):
			mp[arr[i]] += 1
		for i in range(n + 1):
			if mp[i] == 2:
				repeat = i
			elif mp[i] == 0:
				missing = i
		return [repeat, missing]


class Solution:

	def findTwoElement(self, arr, n):
		repeat = -1
		missing = -1
		for i in range(n):
			if arr[abs(arr[i]) - 1] > 0:
				arr[abs(arr[i]) - 1] = -arr[abs(arr[i]) - 1]
			else:
				repeat = abs(arr[i])
		for i in range(n):
			if arr[i] > 0:
				missing = i + 1
		return [repeat, missing]


class Solution:

	def findTwoElement(self, arr, n):
		val_hash = {}
		answer = []
		actual_sum = int(n * (n + 1) / 2)
		sum = 0
		for val in arr:
			if val_hash.get(val, 0) != 1:
				sum += val
				val_hash[val] = 1
			else:
				answer.append(val)
		answer.append(actual_sum - sum)
		return answer


class Solution:

	def findTwoElement(self, arr, n):
		t = n * (n + 1) // 2
		s1 = sum(set(arr))
		s2 = sum(arr)
		k = s2 - s1
		p = t - s1
		return (k, p)


class Solution:

	def findTwoElement(self, arr, n):

		def repeatNumber(arr):
			mp = {}
			for element in arr:
				if element not in mp:
					mp[element] = element
				else:
					return element
		sm = sum(arr)
		oneToN = [i for i in range(1, n + 1)]
		smOneToN = sum(oneToN)
		eq = sm - smOneToN
		rptNumber = repeatNumber(arr)
		msgNumber = rptNumber - eq
		return [rptNumber, msgNumber]


class Solution:

	def findTwoElement(self, arr, n):
		s = n * (n + 1) // 2
		s2 = n * (n + 1) * (2 * n + 1) // 6
		asum = 0
		a2sum = 0
		for ele in arr:
			asum += ele
			a2sum += ele * ele
		val1 = asum - s
		val2 = a2sum - s2
		val2 = val2 // val1
		x = (val1 + val2) // 2
		y = x - val1
		return [x, y]


class Solution:

	def findTwoElement(self, arr, n):
		ans = [0] * 2
		for i in range(n):
			if arr[abs(arr[i]) - 1] > 0:
				arr[abs(arr[i]) - 1] = -arr[abs(arr[i]) - 1]
			else:
				ans[0] = abs(arr[i])
		for i in range(n):
			if arr[i] > 0:
				ans[1] = i + 1
		return ans


class Solution:

	def findTwoElement(self, arr, n):
		for i in range(n):
			arr[arr[i] % n - 1] += n
		missing = -1
		repated = -1
		for i in range(n):
			if arr[i] <= n:
				missing = i + 1
			if arr[i] > 2 * n:
				repated = i + 1
		return [repated, missing]


class Solution:

	def findTwoElement(self, arr, n):
		missing = 0
		dup = 0
		local_dict = dict.fromkeys(arr, 0)
		for item in arr:
			local_dict[item] += 1
		for number in range(1, n + 1):
			if not local_dict.get(number):
				missing = number
			elif local_dict[number] == 2:
				dup = number
		return [dup, missing]


from collections import Counter

class Solution:

	def findTwoElement(self, arr, n):
		A = Counter(arr)
		B = 0
		for (i, j) in A.items():
			if j > 1:
				B = i
		A = sum(arr) - B
		total = n * (n + 1) // 2
		A = total - A
		return (B, A)


class Solution:

	def findTwoElement(self, arr, n):
		sumn = n * (n + 1) / 2
		sumsn = n * (n + 1) * (2 * n + 1) / 6
		sumi = sum(arr)
		sums = 0
		for i in range(n):
			sums += arr[i] * arr[i]
		val1 = sumi - sumn
		val2 = sums - sumsn
		val2 = val2 / val1
		x = (val1 + val2) / 2
		y = x - val1
		return (int(x), int(y))


class Solution:

	def findTwoElement(self, arr, n):
		h = [0] * (n + 1)
		for i in range(n):
			h[arr[i]] += 1
		mi = -1
		twi = -1
		for i in range(1, n + 1):
			if h[i] == 2:
				twi = i
			elif h[i] == 0:
				mi = i
			if mi != -1 and twi != -1:
				break
		return (twi, mi)


class Solution:

	def findTwoElement(self, arr, n):
		from collections import defaultdict
		ans = []
		m = defaultdict(int)
		for i in range(1, n + 1):
			m[i] = 0
		for i in arr:
			m[i] += 1
		for (k, v) in m.items():
			if v == 2:
				ans.append(k)
		for (k, v) in m.items():
			if v == 0:
				ans.append(k)
		return ans


import math

class Solution:

	def findTwoElement(self, arr, n):
		sumArr = sum(arr)
		repeatingEle = 0
		for i in range(n):
			ele = abs(arr[i])
			if arr[ele - 1] > 0:
				arr[ele - 1] = -1 * arr[ele - 1]
			else:
				repeatingEle = ele
				break
		sumN = n * (n + 1) // 2
		missingEle = sumN - sumArr + repeatingEle
		return (repeatingEle, missingEle)


class Solution:

	def findTwoElement(self, arr, n):
		A = set(range(1, n + 1))
		mis = list(A - set(arr))[0]
		dic = {}
		for i in arr:
			if i not in dic:
				dic[i] = 0
			dic[i] += 1
		for (key, val) in dic.items():
			if val == 2:
				return [key, mis]


class Solution:

	def findTwoElement(self, arr, n):
		s = n * (n + 1) // 2
		p = n * (n + 1) * (2 * n + 1) // 6
		missing = 0
		repeating = 0
		ans = []
		for i in arr:
			s -= i
			p -= i * i
		missing = (s + p // s) // 2
		repeating = missing - s
		ans.append(repeating)
		ans.append(missing)
		return ans


class Solution:

	def findTwoElement(self, arr, n):
		x = []
		arr.sort()
		c = arr[0]
		for i in range(1, n):
			c += arr[i]
			if arr[i] == arr[i - 1]:
				x.append(arr[i])
		c = c - x[0]
		sum = n * (n + 1) // 2
		x.append(sum - c)
		return x


class Solution:

	def findTwoElement(self, arr, n):
		arr_set = set()
		repeated_num = 0
		missing_num = 0
		for num in arr:
			if num not in arr_set:
				arr_set.add(num)
			else:
				repeated_num = num
		for i in range(1, n + 1):
			if i not in arr_set:
				missing_num = i
				break
		result = (repeated_num, missing_num)
		return result


class Solution:

	def findTwoElement(self, arr, n):
		ans = [0, 0]
		l = [i for i in range(1, n + 1)]
		ans[1] = sum(l) - sum(set(arr))
		ans[0] = sum(arr) + ans[1] - sum(l)
		return ans


class Solution:

	def findTwoElement(self, arr, n):
		(missing, repeating) = (None, None)
		for i in range(len(arr)):
			if arr[abs(arr[i]) - 1] < 0:
				repeating = abs(arr[i])
			else:
				arr[abs(arr[i]) - 1] *= -1
		for i in range(len(arr)):
			if arr[i] > 0:
				missing = i + 1
		return [repeating, missing]


class Solution:

	def findTwoElement(self, arr, n):
		counter = {}
		for num in arr:
			if num in counter:
				a = num
			else:
				counter[num] = 1
		b = [0] * n
		for num in arr:
			b[num - 1] = 1
		x = []
		for i in range(n):
			if b[i] == 0:
				x.append(i + 1)
		x.append(a)
		return (a, x[0])


class Solution:

	def findTwoElement(self, arr, n):
		freq = [0] * (n + 1)
		missing_num = 0
		repeated_num = 0
		for i in range(n):
			freq[arr[i]] += 1
		for i in range(1, n + 1):
			if freq[i] == 0:
				missing_num = i
			elif freq[i] == 2:
				repeated_num = i
		return (repeated_num, missing_num)


class Solution:

	def findTwoElement(self, arr, n):
		freq = [0] * n
		for i in range(n):
			freq[arr[i] - 1] += 1
		return (freq.index(2) + 1, freq.index(0) + 1)


class Solution:

	def findTwoElement(self, arr, n):
		ans = [0] * n
		r = [-1, -1]
		for i in range(len(arr)):
			ans[arr[i] - 1] += 1
		for i in range(len(ans)):
			if ans[i] == 0:
				r[1] = i + 1
			if ans[i] == 2:
				r[0] = i + 1
		return r


class Solution:

	def findTwoElement(self, arr, n):
		SN = n * (n + 1) // 2
		S2N = n * (n + 1) * (2 * n + 1) // 6
		(missingNum, repeatingNum) = (0, 0)
		for i in range(n):
			SN -= arr[i]
			S2N -= arr[i] * arr[i]
		missingNum = (SN + S2N // SN) // 2
		repeatingNum = missingNum - SN
		ans = []
		ans.append(repeatingNum)
		ans.append(missingNum)
		return ans


class Solution:

	def findTwoElement(self, arr, n):
		n = len(arr)
		seen = set()
		repeating_num = missing_num = None
		for num in arr:
			if num in seen:
				repeating_num = num
			seen.add(num)
		for i in range(1, n + 1):
			if i not in seen:
				missing_num = i
				break
		return (repeating_num, missing_num)


class Solution:

	def findTwoElement(self, arr, n):
		l = [0 for i in range(len(arr))]
		for i in arr:
			l[i - 1] += 1
		return [l.index(2) + 1, l.index(0) + 1]


from collections import *

class Solution:

	def findTwoElement(self, arr, n):
		A = set(range(1, n + 1))
		B = set(arr)
		missing = list(A - B)[0]
		dic = Counter(arr)
		twice = 0
		for (key, val) in dic.items():
			if val == 2:
				twice = key
				break
		return [twice, missing]


class Solution:

	def findTwoElement(self, a, n):
		n = len(a)
		SN = n * (n + 1) // 2
		S2N = n * (n + 1) * (2 * n + 1) // 6
		(S, S2) = (0, 0)
		for i in range(n):
			S += a[i]
			S2 += a[i] * a[i]
		val1 = S - SN
		val2 = S2 - S2N
		val2 = val2 // val1
		x = (val1 + val2) // 2
		y = x - val1
		return [x, y]


class Solution:

	def findTwoElement(self, arr, n):
		d = {}
		ans = []
		for i in arr:
			if i not in d:
				d[i] = 1
			else:
				d[i] += 1
				ans.append(i)
		k = range(1, n + 1)
		k = set(k).difference(set(arr))
		for i in k:
			ans.append(i)
		return ans


class Solution:

	def findTwoElement(self, A, n):
		(x, y) = (None, None)
		n = len(A)
		a = n * (n + 1) // 2
		a_dashed = sum(A)
		b = n * (n + 1) * (2 * n + 1) // 6
		b_dashed = 0
		for i in A:
			b_dashed += i * i
		rel1 = a - a_dashed
		rel2 = b - b_dashed
		rel3 = rel2 // rel1
		y = (rel3 + rel1) // 2
		x = y - rel1
		return [x, y]


class Solution:

	def findTwoElement(self, arr, n):
		sumofn = n * (n + 1) // 2
		sumsetarr = sum(set(arr))
		sumarr = sum(arr)
		missingnumber = sumofn - sumsetarr
		repeatednumber = sumarr - sumsetarr
		return [repeatednumber, missingnumber]


class Solution:

	def get_duplicate(self, arr, n):
		for i in range(n):
			idx = abs(arr[i]) - 1
			if arr[idx] < 0:
				return idx + 1
			arr[idx] = -arr[idx]
		return -1

	def get_missing(self, arr, n):
		for i in range(n):
			idx = abs(arr[i]) - 1
			if arr[idx] > 0:
				arr[idx] = -arr[idx]
		for i in range(n):
			if arr[i] > 0:
				return i + 1

	def findTwoElement(self, arr, n):
		duplicate = self.get_duplicate(arr, n)
		missing = self.get_missing(arr, n)
		return (duplicate, missing)


class Solution:

	def findTwoElement(self, arr, n):
		v = n * (n + 1) // 2
		g = sum(arr)
		j = set(arr)
		rep_element = g - sum(j)
		missing_element = v - sum(j)
		return (rep_element, missing_element)


class Solution:

	def findTwoElement(self, arr, n):
		(d, l, repeated_elem) = ({}, list(range(1, n + 1)), -1)
		for elem in arr:
			d.update({elem: d.get(elem, 0) + 1})
			if d[elem] == 2:
				repeated_elem = elem
		if repeated_elem == -1:
			return [0, 0]
		for elem in l:
			if elem not in d:
				return [repeated_elem, elem]


class Solution:

	def findTwoElement(self, arr, n):
		repeatingElement = 0
		missingElement = 0
		for i in range(len(arr)):
			if arr[abs(arr[i]) - 1] > 0:
				arr[abs(arr[i]) - 1] = -arr[abs(arr[i]) - 1]
			else:
				repeatingElement = abs(arr[i])
		incrCount = 0
		decrCount = 0
		for i in range(len(arr)):
			if arr[i] > 0:
				missingElement = i + 1
		return [repeatingElement, missingElement]


class Solution:

	def findTwoElement(self, arr, n):
		xor = 0
		for i in range(n):
			xor = xor ^ arr[i]
			xor = xor ^ i + 1
		while xor & xor - 1 != 0:
			xor = xor & xor - 1
		a = 0
		b = 0
		for i in range(n):
			if arr[i] & xor:
				a = a ^ arr[i]
			else:
				b = b ^ arr[i]
			if i + 1 & xor:
				a = a ^ i + 1
			else:
				b = b ^ i + 1
		if a in arr:
			return [a, b]
		return [b, a]


from collections import Counter

class Solution:

	def findTwoElement(self, arr, n):
		A = Counter(arr)
		(re, mi) = (-1, -1)
		for i in range(1, n + 1):
			if A[i] == 1:
				pass
			elif A[i] == 2:
				re = i
			else:
				mi = i
		return [re, mi]


class Solution:

	def findTwoElement(self, arr, n):
		arr.sort()
		repeat = 0
		for i in range(n - 1):
			if arr[i] == arr[i + 1]:
				repeat = arr[i]
		arr2 = set([i for i in range(1, n + 1)])
		arr = set(arr)
		missing = arr2.difference(arr)
		miss = 0
		for i in missing:
			miss = i
		return (repeat, miss)


class Solution:

	def findTwoElement(self, arr, n):
		obj = {}
		lst = [0 for x in range(0, n + 2)]
		repeating_num = None
		missing_num = None
		for i in arr:
			if repeating_num is None:
				try:
					obj[i] = obj[i] + i
					repeating_num = i
				except:
					obj[i] = i
			try:
				lst[i] = i
			except:
				pass
		missing_num = lst[1:].index(0) + 1
		return (repeating_num, missing_num)


class Solution:

	def findTwoElement(self, arr, n):
		s_arr = sum(arr)
		s_arr_ele_sq = sum([ele ** 2 for ele in arr])
		s_n_natural_no = n * (n + 1) // 2
		s_sq_n_natural_no = n * (n + 1) * (2 * n + 1) // 6
		x_minus_y = s_n_natural_no - s_arr
		x_sq_minus_y_sq = s_sq_n_natural_no - s_arr_ele_sq
		x_plus_y = x_sq_minus_y_sq // x_minus_y
		x = (x_plus_y + x_minus_y) // 2
		y = (x_plus_y - x_minus_y) // 2
		return [y, x]


class Solution:

	def findTwoElement(self, arr, n):
		map = {}
		for i in range(n):
			if arr[i] not in map:
				map[arr[i]] = True
			else:
				x = arr[i]
		for i in range(1, n + 1):
			if i not in map:
				l = i
		return [x, l]


class Solution:

	def findTwoElement(self, arr, n):
		a = {}
		c = 0
		d = 0
		for i in arr:
			if i in a:
				a[i] += 1
			else:
				a[i] = 1
		count = 1
		while count < len(arr) + 1:
			if count in a:
				if a[count] == 2:
					c = count
			if count not in a:
				d = count
			count += 1
		return (c, d)


class Solution:

	def findTwoElement(self, arr, n):
		result = []
		dict = {}
		for i in arr:
			if i in dict:
				result.append(i)
			else:
				dict[i] = 1
		res = n * (n + 1) // 2 - sum(set(arr))
		result.append(res)
		return result


class Solution:

	def findTwoElement(self, arr, n):
		a = [0] * (n + 1)
		res = 0
		mis = 0
		for idx in range(n):
			a[arr[idx]] += 1
		for idx in range(1, len(a)):
			if a[idx] == 0:
				mis = idx
			if a[idx] > 1:
				res = idx
		return (res, mis)


class Solution:

	def findTwoElement(self, nums, n):
		for i in range(len(nums)):
			while nums[i] > 0 and nums[i] <= n and (nums[nums[i] - 1] != nums[i]):
				(nums[nums[i] - 1], nums[i]) = (nums[i], nums[nums[i] - 1])
		for i in range(n):
			if arr[i] != i + 1:
				return [arr[i], i + 1]


class Solution:

	def findTwoElement(self, arr, n):
		l = []
		a = [0] * n
		for i in arr:
			if a[i - 1] > 0:
				l.append(i)
			a[i - 1] += 1
		for i in range(n):
			if a[i] == 0:
				l.append(i + 1)
		return l


class Solution:

	def findTwoElement(self, arr, n):
		sum1 = sum(arr)
		sum2 = n * (n + 1) // 2
		z1 = sum1 - sum2
		sum3 = 0
		for i in arr:
			sum3 += i * i
		sum4 = 0
		for j in range(1, n + 1):
			sum4 = sum4 + j * j
		z2 = (sum3 - sum4) // z1
		r = (z1 + z2) // 2
		m = r - z1
		return [r, m]


class Solution:

	def findTwoElement(self, arr, n):
		arr.sort()
		l = [0, 0]
		miss = 1
		for i in range(0, len(arr)):
			if arr[i] == miss:
				miss += 1
		l[1] = miss
		for i in range(1, n):
			if arr[i - 1] == arr[i]:
				l[0] = arr[i]
				break
		return l


class Solution:

	def findTwoElement(self, arr, n):
		RmM = sum(arr) - n * (n + 1) // 2
		R2mM2 = sum([x * x for x in arr]) - n * (n + 1) * (2 * n + 1) // 6
		RpM = R2mM2 // RmM
		return [(RpM + RmM) // 2, (RpM - RmM) // 2]


class Solution:

	def findTwoElement(self, arr, n):
		mpp = {}
		li = []
		for i in arr:
			if i not in mpp:
				mpp[i] = 0
			else:
				mpp[i] += 1
		for i in range(1, n + 1):
			try:
				mpp[i] += 1
			except:
				mpp[i] = 0
		for i in mpp:
			if mpp[i] > 1:
				li.append(i)
				break
		for i in mpp:
			if mpp[i] == 0:
				li.append(i)
				break
		return li


class Solution(object):

	def findTwoElement1(self, nums, n):
		lookup = [0] * (n + 1)
		for num in nums:
			lookup[num] += 1
		result = [None, None]
		for num in range(1, n + 1):
			if lookup[num] == 0:
				result[1] = num
			elif lookup[num] > 1:
				result[0] = num
		return result

	def findTwoElement(self, nums, n):
		sumRepeating = 0
		sumMissing = n * (n + 1) // 2
		sumSquareRepeating = 0
		sumSquareMissing = n * (n + 1) * (2 * n + 1) // 6
		for num in nums:
			sumRepeating += num
			sumSquareRepeating += num * num
		val1 = sumRepeating - sumMissing
		val2 = sumSquareRepeating - sumSquareMissing
		val2 = val2 // val1
		x = (val1 + val2) // 2
		y = x - val1
		return [x, y]


class Solution:

	def findTwoElement(self, nums, n):
		sumRepeating = 0
		sumMissing = n * (n + 1) // 2
		sumSquareRepeating = 0
		sumSquareMissing = n * (n + 1) * (2 * n + 1) // 6
		for num in nums:
			sumRepeating += num
			sumSquareRepeating += num * num
		val1 = sumRepeating - sumMissing
		val2 = sumSquareRepeating - sumSquareMissing
		val2 = val2 // val1
		x = (val1 + val2) // 2
		y = x - val1
		return [x, y]


class Solution(object):

	def findTwoElement(self, nums, n):
		lookup = [0] * (n + 1)
		for num in nums:
			lookup[num] += 1
		result = [None, None]
		for num in range(1, n + 1):
			if lookup[num] == 0:
				result[1] = num
			elif lookup[num] > 1:
				result[0] = num
		return result


class Solution:

	def findTwoElement(self, arr, n):
		repeating_element = -1
		missing_element = -1
		for i in range(n):
			index = abs(arr[i]) - 1
			if arr[index] < 0:
				repeating_element = abs(arr[i])
			else:
				arr[index] = -arr[index]
		for i in range(n):
			if arr[i] > 0:
				missing_element = i + 1
				break
		return [repeating_element, missing_element]


class Solution:

	def findTwoElement(self, arr, n):
		d = {}
		l = []
		for i in arr:
			if i not in d:
				d[i] = 1
			else:
				d[i] += 1
				l.append(i)
		for i in range(1, n + 1):
			if i not in d:
				l.append(i)
				return l


class Solution:

	def findTwoElement(self, arr, n):
		h = set()
		dict1 = {}
		lst = []
		for i in range(1, n + 1):
			h.add(i)
		for i in arr:
			if i in dict1:
				dict1[i] = dict1[i] + 1
			else:
				dict1[i] = 1
			if dict1[i] == 2:
				lst.append(i)
		for i in h:
			if i not in dict1:
				lst.append(i)
		return lst


import math

class Solution:

	def findTwoElement(self, arr, n):
		sr = 0
		srr = 0
		su = 0
		sur = 0
		for i in range(n):
			sr += (i + 1) ** 2
			srr += arr[i] ** 2
			su += i + 1
			sur += arr[i]
		s1 = sr - srr
		m_r = su - sur
		m = round((s1 + m_r ** 2) / (2 * m_r))
		r = m - m_r
		return [r, m]


class Solution:

	def findTwoElement(self, arr, n):
		l = []
		arr.sort()
		d = {}
		for i in arr:
			if i not in d:
				d[i] = 1
			else:
				d[i] = d[i] + 1
		for (key, value) in d.items():
			if d[key] == 2:
				l.append(key)
		s = 0
		s1 = 0
		for i in range(1, n + 1):
			s = s + i
		for i in range(n):
			s1 = s1 + arr[i]
		diff = s - (s1 - l[0])
		l.append(diff)
		return l


class Solution:

	def findTwoElement(self, arr, n):
		ans = [0, 0]
		x = n * (n + 1) // 2
		x2 = n * (n + 1) * (2 * n + 1) // 6
		y = 0
		y2 = 0
		for i in arr:
			y += i
			y2 += i ** 2
		e1 = x - y
		e2 = (x2 - y2) // e1
		ans[1] = (e1 + e2) // 2
		ans[0] = (e2 - e1) // 2
		return ans


class Solution:

	def findTwoElement(self, arr, n):
		missing = 0
		duplicate = 0
		seen = set()
		for i in range(n):
			if arr[i] in seen:
				duplicate = arr[i]
				break
			seen.add(arr[i])
		arr_sum = 0
		for i in range(n):
			arr_sum += arr[i]
		arr_sum -= duplicate
		missing = n * (n + 1) // 2 - arr_sum
		return [duplicate, missing]


class Solution:

	def findTwoElement(self, arr, n):
		d = {}
		for i in range(n):
			d[i + 1] = 0
		for ele in arr:
			d[ele] += 1
		return (max(d, key=d.get), min(d, key=d.get))
		while i < n:
			if arr[i] != arr[arr[i] - 1]:
				temp = arr[i]
				arr[i] = arr[arr[i] - 1]
				arr[arr[i] - 1] = temp
			else:
				i += 1
		for i in range(n):
			if arr[i] != arr[arr[i] - 1]:
				return (arr[i], i + 1)


class Solution:

	def findTwoElement(self, arr, n):
		res = []
		for i in range(n):
			if arr[abs(arr[i]) - 1] > 0:
				arr[abs(arr[i]) - 1] = -arr[abs(arr[i]) - 1]
			else:
				res.append(abs(arr[i]))
		for i in range(n):
			if arr[i] > 0:
				res.append(i + 1)
		return res


class Solution:

	def findTwoElement(self, arr, n):
		d = {}
		for i in range(n):
			d[i + 1] = 0
		for ele in arr:
			d[ele] += 1
		return (max(d, key=d.get), min(d, key=d.get))


class Solution:

	def findTwoElement(self, arr, n):
		res = []
		for i in range(0, n):
			while arr[i] - 1 != i:
				j = arr[i] - 1
				(arr[i], arr[j]) = (arr[j], arr[i])
				if arr[i] == arr[j]:
					break
		for i in range(0, n):
			if arr[i] - 1 != i:
				res.append(arr[i])
				res.append(i + 1)
		return res


class Solution:

	def findTwoElement(self, arr, n):
		Nsum = n * (n + 1) / 2
		realSum = sum(arr)
		den = Nsum - realSum
		sqSum = 0
		for i in arr:
			sqSum += i * i
		realSq = n * (n + 1) * (2 * n + 1) / 6
		num = realSq - sqSum
		s = num / den
		missing = (s + den) / 2
		repeat = s - missing
		return [int(repeat), int(missing)]


class Solution:

	def findTwoElement(self, arr, n):
		a_b = n * (n + 1) // 2 - sum(arr)
		a2_b2 = n * (n + 1) * (2 * n + 1) // 6 - sum([x ** 2 for x in arr])
		a = (a2_b2 + a_b ** 2) // (2 * a_b)
		return [a - a_b, a]


from collections import Counter

class Solution:

	def findTwoElement(self, arr, n):
		hm = Counter(arr)
		a = [0] * 2
		for i in range(1, n + 1):
			if i not in hm:
				a[1] = i
			if hm[i] > 1:
				a[0] = i
		return a


class Solution:

	def findTwoElement(self, arr, n):
		arr.sort()
		A = []
		for i in range(len(arr) - 1):
			if arr[i] == arr[i + 1]:
				A.append(arr[i])
				break
		a = set(arr)
		arr = list(a)
		N = n * (n + 1) // 2
		sum1 = 0
		for i in range(len(arr)):
			sum1 += arr[i]
		A.append(N - sum1)
		return A


class Solution:

	def findTwoElement(self, arr, n):
		N = n
		sum_N = n * (n + 1) // 2
		sum_N_squares = n * (n + 1) * (2 * n + 1) // 6
		sum_arr = sum(arr)
		sum_arr_squares = sum((x ** 2 for x in arr))
		diff_sum = sum_N - sum_arr
		diff_sum_squares = sum_N_squares - sum_arr_squares
		repeating = (diff_sum_squares // diff_sum - diff_sum) // 2
		missing = diff_sum + repeating
		return [repeating, missing]


class Solution:

	def findTwoElement(self, arr, n):
		a = []
		b = [0, 0]
		for i in range(1, n + 1):
			a.append(i)
		b[1] = sum(a) - sum(set(arr))
		b[0] = sum(arr) + b[1] - sum(a)
		return b


class Solution:

	def findTwoElement(self, arr, n):
		freq = [0] * (10 ** 5 + 1)
		for num in arr:
			freq[num] += 1
		result = [0] * 2
		for i in range(1, n + 1):
			if freq[i] == 0:
				result[1] = i
			if freq[i] == 2:
				result[0] = i
		return result