Struggling To Understand These 2 Python Files - Printable Version +- Python Forum (https://python-forum.io) +-- Forum: Python Coding (https://python-forum.io/forum-7.html) +--- Forum: Homework (https://python-forum.io/forum-9.html) +--- Thread: Struggling To Understand These 2 Python Files (/thread-29830.html) |
Struggling To Understand These 2 Python Files - samlee916 - Sep-22-2020 Please help me understand the code and its output Find the missing element: Given a sorted list or array, find a more efficient way to identify the element that is missing. Below are code snippets from two files (findMissing.py and findMissingTest.py), create a directory with these files and code snippets in them. If you run “python -m unittest findMissingTest” from terminal or cmd you should see the test fail. Modify the function in “findMissing.py” to make the test pass. findMissing.py #the idea here was to get mid of the array #now if the distance of mid from starting is not equal to distance of starting, #it means missing element is left side #similarly it may be on right side #if not the case in both the answer will be no missing element def findMissing(arr): #get start index start = 0 #get end index end = len(arr) - 1 #get mid mid = 0 #loop until start +1 is less than end while (start + 1 < end): #floor division mid = (start + end) // 2 #If the missing number is less than mid, go through the left side if (arr[start] - start) != (arr[mid] - mid): end = mid #else missing number is on the right side elif (arr[end] - end) != (arr[mid] - mid): start = mid if(start + 1 == end): return arr[mid] + 1 raise ValueError(msg = "No missing element")findMissingTest.py import unittest from timeit import default_timer from sys import version_info from findMissing import findMissing class StringCalculatorTests(unittest.TestCase): def test_findMissing(self): missing = 60000123 print("Missing element actual : "+str(missing)) arr = list(range(100000000)) arr.remove(missing) start_time = default_timer() result = findMissing(arr) end_time = default_timer() print("Algo Missing element : "+str(result)) print("Time took to find missing element is : %15f"%(end_time-start_time)+" seconds") if version_info.major == 2: self.assertGreater(2, end_time - start_time) elif version_info.major == 3: self.assertGreater(2.5, end_time - start_time) self.assertEqual(missing, result)Output: PS C:\Users\slee5\Desktop\Code> python -m unittest findMissingTest.py Missing element actual : 60000123 Algo Missing element : 60000123 Time took to find missing element is : 0.008799 seconds . ---------------------------------------------------------------------- Ran 1 test in 25.192s OK PS C:\Users\slee5\Desktop\Code> RE: Struggling To Understand These 2 Python Files - Gribouillis - Sep-22-2020 The idea is easy to understand, take the list [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]If you remove 0, 1, 2, 3 or 4, then L[4] has value 5. On the other hand, if you remove 5, 6, 7, 8 or 9, then L[4] has value 4. Hence by checking the value of L[4], you can say if the missing value is in range(0, 5) or in range(5, 10). The algorithm then repeats the same argument for the subarrays. RE: Struggling To Understand These 2 Python Files - ndc85430 - Sep-22-2020 It looks like the test is already passing. The output doesn't show a failure. |