daily pastebin goal
74%
SHARE
TWEET

Untitled

a guest Mar 25th, 2019 55 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. OK, I Understand
 
Top