Added one more solution for find_first_missing_positive.py

Мето Трајковски · Мето Трајковски · commit 77c0b0c28b6f · 2019-12-22T19:03:57.000+01:00
diff --git a/Arrays/find_first_missing_positive.py b/Arrays/find_first_missing_positive.py
@@ -13,34 +13,62 @@
 Output: 3
 
 =========================================
-Play with indicies and mark them, a marked index means that the number equals to that index exist in the array.
+Move all values to their positions (val position = val - 1), in the end find the first
+position which doesn't have the needed value.
+    Time Complexity:    O(N)    , maybe nested loops look like O(N^2) but that not true
+    Space Complexity:   O(1)
+Play with indicies and mark them (make it negative),
+a marked index means that the number equals to that index exist in the array.
     Time Complexity:    O(N)
     Space Complexity:   O(1)
 '''
 
 
-############
-# Solution #
-############
+##############
+# Solution 1 #
+##############
+
+def find_first_missing_1(a):
+    n = len(a)
+
+    for i in range(n):
+        while (a[i] > 0) and (a[i] <= n):
+            swap = a[i] - 1
+            if a[i] == a[swap]:
+                break
+
+            # swap elements
+            temp = a[i]
+            a[i] = a[swap]
+            a[swap] = temp
+
+    for i in range(n):
+        if a[i] - 1 != i:
+            return i + 1
+
+    return n + 1
+
 
-def find_first_missing(a):
+##############
+# Solution 2 #
+##############
+
+def find_first_missing_2(a):
     n = len(a)
 
     # eliminate all zeros and all negative numbers
     for i in range(n):
-        if a[i] < 1:
-            a[i] = n + 1 # those elements aren't used later
+        if a[i] <= 0:
+            a[i] = n + 1 # those values won't be used later
 
     # find all numbers in the range and mark all numbers at those positions as negative numbers
-    for i in range(len(a)):
+    for i in range(n):
         idx = abs(a[i]) - 1
         if idx >= n:
             continue
-        val = a[idx]
 
-        if val > 0:
-            # mark element as found for the first time
-            a[idx] = -val
+        # mark the element as found
+        a[idx] = -abs(a[idx])
 
     # find the first non-negative position
     for i in range(n):
@@ -57,34 +85,47 @@ def find_first_missing(a):
 # Test 1
 # Correct result => 1
 test = [-1, 2, 3]
-print(find_first_missing(test))
+print(find_first_missing_1(list(test))) # make a copy, the list will be changed inside the function
+print(find_first_missing_2(list(test)))
 
 # Test 2
 # Correct result => 2
 test = [3, 4, -1, 1]
-print(find_first_missing(test))
+print(find_first_missing_1(list(test)))
+print(find_first_missing_2(list(test)))
 
 # Test 3
 # Correct result => 3
 test = [1, 2, 0]
-print(find_first_missing(test))
+print(find_first_missing_1(list(test)))
+print(find_first_missing_2(list(test)))
 
 # Test 4
 # Correct result => 4
 test = [1, 2, 3]
-print(find_first_missing(test))
+print(find_first_missing_1(list(test)))
+print(find_first_missing_2(list(test)))
 
 # Test 5
 # Correct result => 5
 test = [-4, -1, -3, -1]
-print(find_first_missing(test))
+print(find_first_missing_1(list(test)))
+print(find_first_missing_2(list(test)))
 
 # Test 6
 # Correct result => 6
 test = [2, 1, 2, -1, 0, 20]
-print(find_first_missing(test))
+print(find_first_missing_1(list(test)))
+print(find_first_missing_2(list(test)))
 
 # Test 7
 # Correct result => 7
 test = [1, 2, 5, 5, 1, 2]
-print(find_first_missing(test))
+print(find_first_missing_1(list(test)))
+print(find_first_missing_2(list(test)))
+
+# Test 8
+# Correct result => 4
+test = [1, 2, 3, 5, 1, 2, 3, 3]
+print(find_first_missing_1(list(test)))
+print(find_first_missing_2(list(test)))
diff --git a/Arrays/find_peak_element.py b/Arrays/find_peak_element.py
@@ -6,11 +6,11 @@
 The array may contain multiple peaks, in that case return the index to any one of the peaks is fine.
 You may imagine that nums[-1] = nums[n] = -∞.
 
-Input: [1,2,3,1]
+Input: [1, 2, 3, 1]
 Output: 2
 Output explanation: 3 is a peak element and your function should return the index number 2.
 
-Input: [1,2,1,3,5,6,4]
+Input: [1, 2, 1, 3, 5, 6, 4]
 Output: 1 or 5
 Output explanation: Your function can return either index number 1 where the peak element is 2, or index number 5 where the peak element is 6.
 
@@ -49,8 +49,8 @@ def find_peak_element(nums):
 
 # Test 1
 # Correct result => 2
-print(find_peak_element([1,2,3,1]))
+print(find_peak_element([1, 2, 3, 1]))
 
 # Test 2
 # Correct result => 1 or 5
-print(find_peak_element([1,2,1,3,5,6,4]))
+print(find_peak_element([1, 2, 1, 3, 5, 6, 4]))
diff --git a/Arrays/min_swaps.py b/Arrays/min_swaps.py
@@ -33,9 +33,10 @@ def min_swaps(a):
     for i in range(n):
         # swap the elements till the right element isn't found
         while a[i] - 1 != i:
+            swap = a[i] - 1
             # swap the elements
-            tmp = a[a[i] - 1]
-            a[a[i] - 1] = a[i]
+            tmp = a[swap]
+            a[swap] = a[i]
             a[i] = tmp
 
             swaps += 1
diff --git a/Arrays/product_of_array_except_self.py b/Arrays/product_of_array_except_self.py
@@ -3,15 +3,13 @@
 
 Given an array nums of n integers where n > 1,
 return an array output such that output[i] is equal to the product of all the elements of nums except nums[i].
-
 Note: Please solve it without division and in O(n).
-
 Follow up:
 Could you solve it with constant space complexity?
 (The output array does not count as extra space for the purpose of space complexity analysis.)
 
-Input: [1,2,3,4]
-Output: [24,12,8,6]
+Input: [1, 2, 3, 4]
+Output: [24, 12, 8, 6]
 
 =========================================
 2 iterations, one from front and the second from back.
@@ -58,4 +56,4 @@ def product_except_self(nums):
 
 # Test 1
 # Correct result => [24, 12, 8, 6]
-print(product_except_self([1,2,3,4]))
+print(product_except_self([1, 2, 3, 4]))
diff --git a/Math/total_divisible_numbers.py b/Math/total_divisible_numbers.py
@@ -31,7 +31,8 @@ def total_divisible_numbers(arr, S):
 
 def gcd(a, b):
     while a != 0:
-        a, b = b % a, a
+        a, b = b % a, a # "Pythonic way"
+        # or temp = a; a = b % a; b = temp; in the other languages
     return b
 
 
diff --git a/Other/nth_fibonacci_number.py b/Other/nth_fibonacci_number.py
@@ -121,7 +121,8 @@ def nth_fibonacci_4(n):
     dp0, dp1 = 0, 1
 
     for i in range(n):
-        dp0, dp1 = dp1, dp0 + dp1
+        dp0, dp1 = dp1, dp0 + dp1 # "Pythonic way"
+        # or dp1 += dp0; dp0 = dp1 - dp0; in other languages
 
     return dp0
 
diff --git a/Other/power.py b/Other/power.py
@@ -16,7 +16,7 @@
 def power(a, b):
     if b < 0:
         # negative power
-        return 1/power_recursive(a, -b)
+        return 1 / power_recursive(a, -b)
 
     return power_recursive(a, b)
 
