-
Notifications
You must be signed in to change notification settings - Fork 81
/
TwoMissingNumbers.py
85 lines (60 loc) · 2.13 KB
/
TwoMissingNumbers.py
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
"""
Title: Two missing
Given an array containing all the numbers from 1 to n except two,
find the two missing numbers.
Execution: python TwoMissing.py
For more details, check out http://www.byte-by-byte.com/twomissing
"""
import unittest
def oneMissing(arr):
totalXor = 0
arrXor = 0
# XOR the numbers from 1 to N, ie. the input if no numbers were missing
for i in range(1, len(arr)+2):
totalXor = totalXor ^ i
# XOR the array
for i in range(len(arr)):
arrXor = arrXor ^ arr[i]
return totalXor ^ arrXor
def twoMissing(arr):
size = len(arr) + 2
totalSum = size * (size + 1)//2 # we want only the integer portion
arrSum = 0
for i in range(len(arr)):
arrSum += arr[i]
pivot = (totalSum - arrSum) // 2 # we want only the integer portion
totalLeftXor = 0
arrLeftXor = 0
totalRightXor = 0
arrRightXor = 0
for i in range(1, pivot+1):
totalLeftXor ^= i
for i in range(pivot+1, size+1):
totalRightXor ^= i
for i in range(len(arr)):
if (arr[i] <= pivot):
arrLeftXor ^= arr[i]
else:
arrRightXor ^= arr[i]
return (totalLeftXor ^ arrLeftXor, totalRightXor ^ arrRightXor)
class TestMissingNumbers(unittest.TestCase):
def test_oneMissing(self):
# oneMissing tests
self.assertEqual(oneMissing([1, 2, 4, 5]), 3)
print "oneMissing: Normal case"
self.assertEqual(oneMissing([3, 2, 5, 4]), 1)
print "oneMissing: Missing first element"
self.assertEqual(oneMissing([4, 3, 2, 1]), 5)
print "oneMissing: Missing last element"
print "Passed all oneMissing test cases"
def test_twoMissing(self):
# twomissing tests
self.assertEqual(twoMissing([1, 3, 5]), (2, 4))
print "\ntwoMissing: Normal case"
self.assertEqual(twoMissing([2, 4, 5]), (1, 3))
print "twoMissing: Missing first element"
self.assertEqual(twoMissing([3, 1, 2]), (4, 5))
print "twoMissing: Missing last two elements"
print "Passed all twoMissing test cases"
if __name__ == '__main__':
unittest.main()