 # DCP40 - No-duplicated number

Sep 28th, 2020
1,109
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
1. '''
2. Given an array of integers where every integer occurs three times except for one integer, which only occurs once, find and return the non-duplicated integer.
3. For example, given [6, 1, 3, 3, 3, 6, 6], return 1. Given [13, 19, 13, 13], return 19.
4. Do this in O(N) time and O(1) space.
5. '''
6. from timeit import default_timer as timer
7. from random import randrange, shuffle, _sha512
8.
9. # Function 1
10. def solve1(myList):
11.     uniques = list()
12.     for i in range(len(myList)):
13.         for unique in uniques:
14.             if myList[i] == unique:
15.                 break
16.         uniques.append(myList[i])
17.
18.     counters = list()
19.     for i in range(len(uniques)):
20.         counters.append(0)
21.     for i in range(len(myList)):
22.         for unique in uniques:
23.             if myList[i] == unique:
24.                 counters[i] += 1
25.
26.     # So, now my counters list is ready
27.     for i in range(len(counters)):
28.         if counters[i] == 1:
29.             return uniques[i]
30.
31. # Function 2
32. def solve2(myList):
33.     myList = sorted(myList)
34.     # Now, that "myList" is sorted, I can compare its element with the previous and next one. If my current element is equal with the previous one and
35.     # the next one, I am sure that this element appears exactly 3 times, so I walk on. Otherwise, I have to return this element.
37.     for i in range(1, len(myList)-1):
38.         if myList[i] != myList[i-1] and myList[i] != myList[i+1]:
40.     # The above code works when this element is only in the MEDIUM positions of the array, otherwise the value of "answer" remains -1000
41.     # This means that maybe the first or last element is the answer
43.         if myList == myList:
44.             # The answer is not in the list's beginning, but in the end
46.         else:
49.
50.
51. # Function 3
52. def prettyPrintWithTime(function, myList):
53.     start = timer()
54.     result = function(myList)
55.     end = timer()
56.     elapsed = 10**6 * (end - start)
57.     print("Using function " + str(function.__name__) + ": " + str(myList) + " ----> " + str(result) + " (" + str(round(elapsed, 2)) + " μs).")
58.
59.
60. # Function 4
61. def generateRandomList(n1, n2):
62.
63.     N = randrange(n1, n2)    # 7 <= N <= 11
64.     # My final list will contain form 7 * 3 + 1 = 22 elements to 11 * 3 + 1 = 34 elements
65.     myList = list()
66.     myList.append(randrange(20))
67.     for i in range(1, N):
68.         r = randrange(myList[len(myList)-1] + 1, myList[len(myList)-1] + 21)
69.         myList.append(r)
70.
71.     # These will be the different elements except the last one, that I will keep it twice
72.     newList = list()
73.     for i in range(len(myList)):
74.         newList.append(myList[i])
75.         newList.append(myList[i])
76.         newList.append(myList[i])
77.     # Last step is to add a brand-new different value
78.     exists = False
79.     new = randrange(200)
80.     for element in myList:
81.         if element == new:
82.             exists = True
83.             break
84.     while exists == True:
85.         new = randrange(200)
86.         for element in myList:
87.             if element == new:
88.                 exists = True
89.                 break
90.     newList.append(new)
91.     shuffle(newList)
92.     return newList
93.
94. # MAIN FUNCTION
95. list1 = [6, 1, 3, 3, 3, 6, 6]
96. list2 = [13, 19, 13, 13]
97. list3 = generateRandomList(7, 12)
98. prettyPrintWithTime(solve1, list1)
99. prettyPrintWithTime(solve2, list1)
100. prettyPrintWithTime(solve1, list2)
101. prettyPrintWithTime(solve2, list2)
102. prettyPrintWithTime(solve1, list3)
103. prettyPrintWithTime(solve2, list3)
RAW Paste Data