You are given an array of N+2 integer elements. All elements of the array are in the range 1 to N. Also, all elements occur once except two numbers which occur twice. Find the two repeating numbers.
Note: Return the numbers in their order of appearing twice. So, if X and Y are the repeating numbers, and X repeats twice before Y repeating twice, then the order should be (X, Y).
Example 1:
Input:
N = 4
array[] = {1,2,1,3,4,3}
Output: 1 3
Explanation: In the given array, 
1 and 3 are repeated two times.
Example 2:
Input:
N = 2
array[] = {1,2,2,1}
Output: 2 1
Explanation: In the given array,
1 and 2 are repeated two times 
and second occurence of 2 comes 
before 1. So the output is 2 1.
Your Task:
The task is to complete the function repeatedElements() which takes array arr[] and an integer N as inputs (the size of the array is N + 2 and elements are in the range[1, N]) and finds the two repeated element in the array and return them in a list.
Expected Time Complexity: O(N).
Expected Auxiliary Space: O(1). 
Constraints: 
2 ≤ N ≤ 10^{5}
1 ≤ array[i] ≤ N

Source: geeksforgeeks | Difficulty: EASY
Tags: Data structures

Complete search

Starter code: #User function Template for python3



class Solution:

    

    #Function to find two repeated elements.

    def twoRepeated(self, arr , N):

        #Your code here

Solutions:
class Solution:

	def twoRepeated(self, arr, N):
		a = []
		for i in range(N + 2):
			arr[arr[i] % (N + 2)] += N + 2
			if arr[arr[i] % (N + 2)] > 2 * N + 4:
				a.append(arr[i % (N + 2)] % (N + 2))
		return a


class Solution:

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


class Solution:

	def twoRepeated(self, arr, N):
		ans = []
		d = {}
		for i in arr:
			if i not in d.keys():
				d[i] = 0
		for i in arr:
			if d[i] == 1:
				ans.append(i)
			else:
				d[i] = d[i] + 1
		return ans


class Solution:

	def twoRepeated(self, arr, N):
		d = {}
		ans = []
		for i in arr:
			if i not in d:
				d[i] = 'inserted'
			else:
				ans.append(i)
		return ans


class Solution:

	def twoRepeated(self, arr, N):
		s = set()
		res = []
		for item in arr:
			if item not in s:
				s.add(item)
			else:
				res.append(item)
		return res


class Solution:

	def twoRepeated(self, arr, N):
		s = set()
		ans = []
		for i in arr:
			if i not in s:
				s.add(i)
			else:
				ans.append(i)
		return ans


class Solution:

	def twoRepeated(self, arr, N):
		b = set()
		c = []
		for i in range(0, N + 2):
			if arr[i] in b:
				c.append(arr[i])
			if arr[i] not in b:
				b.add(arr[i])
		return c


class Solution:

	def twoRepeated(self, arr, N):
		x = set()
		res = []
		for i in arr:
			if i not in x:
				x.add(i)
			else:
				res.append(i)
		return res


class Solution:

	def twoRepeated(self, arr, N):
		mp = {i: 0 for i in arr}
		ans = []
		for i in arr:
			mp[i] += 1
			if mp[i] >= 2:
				ans.append(i)
		return ans


from typing import List

class Solution:

	def twoRepeated(self, arr, N):
		a = []
		s = set()
		for i in arr:
			if i not in s:
				s.add(i)
			else:
				a.append(i)
		return a


class Solution:

	def twoRepeated(self, arr, N):
		freq = [0] * (N + 1)
		ans = []
		for x in arr:
			freq[x] += 1
			if freq[x] == 2:
				ans.append(x)
		return ans


class Solution:

	def twoRepeated(self, arr, N):
		n1 = n2 = -1
		dic = {}
		for i in arr:
			if dic.get(i) == None:
				dic[i] = 1
			elif dic[i] == 1:
				if n1 == -1:
					n1 = i
				elif n2 == -1:
					n2 = i
		return (n1, n2)


class Solution:

	def twoRepeated(self, arr, N):
		b = {}
		a = []
		for i in range(len(arr)):
			if arr[i] not in b:
				b[arr[i]] = 1
			elif arr[i] in b:
				a.append(arr[i])
		return a


class Solution:

	def twoRepeated(self, arr, N):
		dict1 = {}
		list1 = []
		for i in arr:
			if i in dict1:
				dict1[i] += 1
			elif i not in dict1:
				dict1[i] = 1
			if dict1[i] == 2:
				list1.append(i)
		return list1


class Solution:

	def twoRepeated(self, arr, N):
		l = []
		d = {}
		d1 = {}
		for i in arr:
			if i in d:
				d[i] += 1
			elif i not in d:
				d[i] = 1
			if d[i] == 2:
				l.append(i)
		return l


class Solution:

	def twoRepeated(self, arr, N):
		d = {}
		l = []
		for i in range(len(arr)):
			if arr[i] not in d:
				d[arr[i]] = 1
			elif arr[i] in d:
				l.append(arr[i])
		return l


class Solution:

	def twoRepeated(self, arr, N):
		d = set()
		r = []
		for i in arr:
			if i not in d:
				d.add(i)
			else:
				r.append(i)
		return r


from collections import Counter

class Solution:

	def twoRepeated(self, arr, size):
		count = [0] * (size + 2)
		res = []
		for i in range(size + 2):
			if count[arr[i]] == 1:
				res.append(arr[i])
			else:
				count[arr[i]] = count[arr[i]] + 1
		return res


class Solution:

	def twoRepeated(self, arr, N):
		unique = {}
		repeated = []
		for i in range(N + 2):
			if arr[i] in unique:
				repeated.append(arr[i])
			else:
				unique[arr[i]] = 1
		return repeated


class Solution:

	def twoRepeated(self, arr, N):
		sorted_arr = sorted(arr)
		reparr = []
		for i in range(N + 1):
			if len(reparr) == 2:
				break
			if sorted_arr[i] == sorted_arr[i + 1]:
				reparr.append(sorted_arr[i])
		arr.remove(reparr[0])
		arr.remove(reparr[1])
		if arr.index(reparr[0]) < arr.index(reparr[1]):
			return reparr
		else:
			reparr.reverse()
			return reparr


class Solution:

	def twoRepeated(self, arr, size):
		count = [0] * (size + 2)
		res = []
		for i in range(0, size + 2):
			if count[arr[i]] == 1:
				res.append(arr[i])
			else:
				count[arr[i]] = count[arr[i]] + 1
		return res


class Solution:

	def twoRepeated(self, arr, N):
		fn = []
		fm = [False] * len(arr)
		for i in range(len(fm)):
			if fm[arr[i]] == True:
				fn.append(arr[i])
			fm[arr[i]] = True
		return fn


class Solution:

	def twoRepeated(self, arr, N):
		a = set()
		b = []
		for i in arr:
			if i not in a:
				a.add(i)
			else:
				b.append(i)
		return b


class Solution:

	def twoRepeated(self, arr, N):
		dic = {}
		c = []
		for i in range(N + 2):
			if arr[i] not in dic:
				dic[arr[i]] = 1
			else:
				dic[arr[i]] += 1
				if dic[arr[i]] == 2:
					c.append(arr[i])
		return c


class Solution:

	def twoRepeated(self, arr, N):
		repeats = []
		seen = {}
		for i in range(0, N + 2):
			if arr[i] not in seen:
				seen[arr[i]] = 0
			seen[arr[i]] = seen[arr[i]] + 1
			if seen[arr[i]] > 1:
				repeats.append(arr[i])
		return repeats


class Solution:

	def twoRepeated(self, arr, N):
		dict = {}
		repeated = []
		for i in arr:
			if i in dict:
				repeated.append(i)
			else:
				dict[i] = 1
		return repeated


class Solution:

	def twoRepeated(self, arr, N):
		d = {}
		for i in arr:
			if i not in d:
				d[i] = 1
			else:
				d[i] += 1
		a = []
		for j in d:
			if d[j] == 2:
				a.append(j)
		for k in range(N + 1, -1, -1):
			if arr[k] in a:
				if arr[k] == a[0]:
					a.reverse()
					return a
				else:
					return a


class Solution:

	def twoRepeated(self, arr, N):
		(D, out) = ({}, [])
		for i in arr:
			D[i] = D.get(i, 0) + 1
			if D.get(i) == 2:
				out.append(i)
		return out


class Solution:

	def twoRepeated(self, arr, N):
		ans = [0, 0]
		j = 0
		for i in range(N + 2):
			if arr[abs(arr[i])] < 0:
				ans[j] = abs(arr[i])
				j += 1
				if j == 2:
					break
			arr[abs(arr[i])] *= -1
		return ans


class Solution:

	def twoRepeated(self, arr, N):
		ls = []
		x = 0
		for i in range(len(arr)):
			if arr[abs(arr[i])] > 0:
				arr[abs(arr[i])] = -1 * arr[abs(arr[i])]
			else:
				ls.append(abs(arr[i]))
		return ls


class Solution:

	def twoRepeated(self, arr, N):
		l1 = set()
		d1 = []
		for i in arr:
			if i not in l1:
				l1.add(i)
			elif i in l1:
				d1.append(i)
		return d1


class Solution:

	def twoRepeated(self, arr, N):
		m = {}
		x = []
		for i in arr:
			if i in m:
				m[i] += 1
				if m[i] >= 2:
					x.append(i)
			else:
				m[i] = 1
		return x


class Solution:

	def twoRepeated(self, arr, N):
		(d, res) = ({}, [])
		for i in arr:
			if i in d:
				res.append(i)
			else:
				d[i] = 1
		return res


class Solution:

	def twoRepeated(self, arr, N):
		hashtable = {}
		ans = []
		for i in arr:
			hashtable[i] = 1 + hashtable.get(i, 0)
		for (key, value) in hashtable.items():
			if value == 2:
				ans.append(key)
				arr.remove(key)
		if arr.index(ans[0]) < arr.index(ans[-1]):
			return ans
		else:
			return ans[::-1]


class Solution:

	def twoRepeated(self, arr, N):
		temp = set()
		st = []
		for item in arr:
			if item not in temp:
				temp.add(item)
			else:
				st.append(item)
		return st


class Solution:

	def twoRepeated(self, arr, N):
		a = []
		d = {}
		for i in arr:
			if i in d:
				d[i] += 1
				if d[i] >= 2:
					a.append(i)
			else:
				d[i] = 1
		return a


class Solution:

	def twoRepeated(self, arr, N):
		index = {}
		res = []
		for i in arr:
			if i in index:
				res.append(i)
			else:
				index.update({i: 1})
		return res


class Solution:

	def twoRepeated(self, arr, N):
		result = []
		for i in range(len(arr)):
			index = abs(arr[i])
			if arr[index - 1] >= 0:
				arr[index - 1] *= -1
			else:
				result.append(index)
		return result


class Solution:

	def twoRepeated(self, arr, N):
		rptd = []
		map = {}
		for i in arr:
			if i not in map:
				map[i] = 1
			else:
				map[i] += 1
				if map[i] == 2:
					rptd.append(i)
		return rptd


class Solution:

	def twoRepeated(self, a, n):
		m = {}
		x = []
		for i in a:
			if i in m:
				m[i] += 1
				if m[i] >= 2:
					x.append(i)
			else:
				m[i] = 1
		return x


class Solution:

	def twoRepeated(self, arr, N):
		mp = {}
		lst = []
		for i in range(0, N + 2):
			if arr[i] in mp:
				if len(lst) <= 2:
					lst.append(arr[i])
				else:
					break
			else:
				mp[arr[i]] = 1
		return lst


class Solution:

	def twoRepeated(self, a, n):
		ans = []
		for i in range(n + 2):
			if a[abs(a[i]) - 1] < 0:
				ans.append(abs(a[i]))
			else:
				a[abs(a[i]) - 1] = -a[abs(a[i]) - 1]
		return ans


from collections import OrderedDict

class Solution:

	def twoRepeated(self, arr, N):
		od = OrderedDict()
		s = []
		for i in arr:
			if i not in od:
				od[i] = 1
			else:
				od[i] += 1
			if od[i] == 2:
				s.append(i)
		return s


class Solution:

	def twoRepeated(self, arr, N):
		j = 0
		res = [0] * 2
		for i in range(len(arr)):
			index = abs(arr[i]) - 1
			arr[index] *= -1
			if arr[index] > 0:
				res[j] = index + 1
				j += 1
		return res


class Solution:

	def twoRepeated(self, arr, N):
		d = {i: 0 for i in arr}
		l = []
		for i in arr:
			d[i] = d[i] + 1
			if d[i] > 1:
				l.append(i)
		return l


class Solution:

	def twoRepeated(self, arr, N):
		l1 = []
		l3 = dict()
		for i in arr:
			if i not in l3.keys():
				l3[i] = 0
			else:
				l3[i] = 1
			if l3.get(i) == 1:
				if i not in l1:
					l1.append(i)
		return l1


class Solution:

	def twoRepeated(self, arr, n):
		s = set()
		res = []
		for i in arr:
			if i not in s:
				s.add(i)
			else:
				res.append(i)
		return res


class Solution:

	def twoRepeated(self, arr, N):
		d = {}
		l = []
		for i in range(N + 1):
			d[i] = 0
		for i in range(0, N + 2, 1):
			d[arr[i]] = d[arr[i]] + 1
			if d[arr[i]] > 1 and arr[i] not in l:
				l.append(arr[i])
		return l


from collections import Counter

class Solution:

	def twoRepeated(self, arr, N):
		s = set()
		li = []
		for i in arr:
			if i not in s:
				s.add(i)
			else:
				li.append(i)
		return li


from collections import Counter as c

class Solution:

	def twoRepeated(self, arr, N):
		s = set()
		res = []
		for item in arr:
			if item not in s:
				s.add(item)
			else:
				res.append(item)
		return res


from collections import Counter

class Solution:

	def twoRepeated(self, arr, N):
		s = set()
		ans = []
		for i in arr:
			if i not in s:
				s.add(i)
			elif i not in ans:
				ans.append(i)
		return ans


class Solution:

	def twoRepeated(self, arr, N):
		a = []
		b = []
		for i in range(0, N + 3):
			x = 0
			a.append(x)
		for i in range(0, N + 2):
			a[arr[i]] = a[arr[i]] + 1
			if a[arr[i]] == 2:
				b.append(arr[i])
		return b


class Solution:

	def twoRepeated(self, arr, N):
		nums = list()
		for x in arr:
			if arr[abs(x)] > 0:
				arr[abs(x)] = -arr[abs(x)]
			else:
				nums.append(abs(x))
		return nums


class Solution:

	def twoRepeated(self, arr, N):
		nums = list()
		m = dict()
		for x in arr:
			m.update({x: m.get(x, 0) + 1})
			if m.get(x) == 2 and x not in nums:
				nums.append(x)
		nums = list(nums)
		return nums