Sep-22-2020, 03:28 AM
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
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>
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>