makispaiktis

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.
  36.     answer = -1000
  37.     for i in range(1, len(myList)-1):
  38.         if myList[i] != myList[i-1] and myList[i] != myList[i+1]:
  39.             answer = myList[i]
  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
  42.     if answer == -1000:
  43.         if myList[0] == myList[1]:
  44.             # The answer is not in the list's beginning, but in the end
  45.             answer = myList[len(myList)-1]
  46.         else:
  47.             answer = myList[0]
  48.     return answer
  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