• API
• FAQ
• Tools
• Archive
SHARE
TWEET Untitled a guest Mar 25th, 2019 56 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
1. import unittest
2.
3. '''Write a function:
4. def solution(A)
5. that, given an array A of N integers, returns the smallest positive integer (greater than 0) that does not occur in A.
6.
7. For example, given A = [1, 3, 6, 4, 1, 2], the function should return 5.
8. Given A = [1, 2, 3], the function should return 4.
9. Given A = [−1, −3], the function should return 1.
10.
11. Write an efficient algorithm for the following assumptions:
12. * N is an integer within the range [1..100,000];
13. * each element of array A is an integer within the range [−1,000,000..1,000,000].
14. '''
15.
16. def solution_a(A):
17.
18.   # If max value in A is negative, just return 1.
19.   if max(A) <= 0 :
20.     return 1
21.
22.   # Make the sorted list with positive integer numbers only.
23.   A.sort()
24.   sorted_positive_list = [ x for x in A if x>0 ]
25.
26.   # Find the list of pair of integer with the difference between two numbers are bigger than 2.
27.   for i in range(len(sorted_positive_list)-1):
28.     diff = sorted_positive_list[i+1] - sorted_positive_list[i]
29.     if diff >= 2:
30.       # Assume the pair is (A, B) and there is the gap, then return A+1
31.       return sorted_positive_list[i]+1
32.   # If no element of this list of pair, just return max(sorted numbers) + 1
33.   return max(sorted_positive_list)+1
34.
35.
36. class TestSolutionA(unittest.TestCase):
37.
38.   # Use code to generate random integer list.
39.   # random.sample(range(-1000000, 1000000), 10)
40.
41.     def test_case0(self):
42.       input_list = [1, 3, 6, 4, 1, 2]
43.       val = solution_a(input_list)
44.       self.assertEqual(val, 5)
45.
46.     def test_case1(self):
47.       input_list = [1, 2, 3]
48.       val = solution_a(input_list)
49.       self.assertEqual(val, 4)
50.
51.     def test_case2(self):
52.       input_list = [ -1, -3]
53.       val = solution_a(input_list)
54.       self.assertEqual(val, 1)
55.
56.     def test_case3(self):
57.       input_list = [100000, 500, 10]
58.       val = solution_a(input_list)
59.       self.assertEqual(val, 11)
60.
61.     def test_case4(self):
62.       input_list = [ -5, -10, -2, 0]
63.       val = solution_a(input_list)
64.       self.assertEqual(val, 1)
65.
66.     def test_case5(self):
67.       input_list = [ -5, -10, -2, 0]
68.       val = solution_a(input_list)
69.       self.assertEqual(val, 1)
70.
71.     def test_case6(self):
72.       input_list = [-266959, -559850, 667410, -370471, -695927, 170911, 658702, -737673, 370182, -285767]
73.       val = solution_a(input_list)
74.       self.assertEqual(val, 170912)
75.
76.     def test_case6(self):
77.       input_list = [860108, 591722, -969778, -439377, -511718,\
78.  -207087, -457298, 908118, 311622, 519103, -975605, -157567,\
79.  -318617, -634176, 264219, -82032, -277682, -364746, -788141,\
80.  584287]
81.       val = solution_a(input_list)
82.       self.assertEqual(val, 264220)
83.
84.
85.
86. if __name__ == '__main__':
87.     unittest.main()
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy.

Top