Add solutions for problems missing_integer, passing_cars

parthnaik7 · parthnaik7 · commit 6207f3b28273 · 2021-09-24T22:22:44.000+05:30
diff --git a/4-counting_elements/missing_integer.py b/4-counting_elements/missing_integer.py
@@ -0,0 +1,34 @@
+"""
+Write a function:
+
+def solution(A)
+
+that, given an array A of N integers, returns the smallest positive integer (greater than 0) that does not occur in A.
+
+For example, given A = [1, 3, 6, 4, 1, 2], the function should return 5.
+
+Given A = [1, 2, 3], the function should return 4.
+
+Given A = [−1, −3], the function should return 1.
+
+Write an efficient algorithm for the following assumptions:
+
+N is an integer within the range [1..100,000];
+each element of array A is an integer within the range [−1,000,000..1,000,000].
+https://app.codility.com/demo/results/training3KJDHP-5MC/
+Time complexity: O(N) or O(N * log(N))
+"""
+
+
+def solution(A):
+    missing = 1
+    for elem in sorted(A):
+        if elem == missing:
+            missing += 1
+        if elem > missing:
+            break
+    return missing
+
+
+s = solution([1, 3, 6, 4, 1, 2])
+print(s)
diff --git a/5-prefix_sums/passing_cars.py b/5-prefix_sums/passing_cars.py
@@ -0,0 +1,59 @@
+"""
+A non-empty array A consisting of N integers is given. The consecutive elements of array A represent consecutive cars on a road.
+
+Array A contains only 0s and/or 1s:
+
+0 represents a car traveling east,
+1 represents a car traveling west.
+The goal is to count passing cars. We say that a pair of cars (P, Q), where 0 ≤ P < Q < N, is passing when P is traveling to the east and Q is traveling to the west.
+
+For example, consider array A such that:
+
+  A[0] = 0
+  A[1] = 1
+  A[2] = 0
+  A[3] = 1
+  A[4] = 1
+We have five pairs of passing cars: (0, 1), (0, 3), (0, 4), (2, 3), (2, 4).
+
+Write a function:
+
+def solution(A)
+
+that, given a non-empty array A of N integers, returns the number of pairs of passing cars.
+
+The function should return −1 if the number of pairs of passing cars exceeds 1,000,000,000.
+
+For example, given:
+
+  A[0] = 0
+  A[1] = 1
+  A[2] = 0
+  A[3] = 1
+  A[4] = 1
+the function should return 5, as explained above.
+
+Write an efficient algorithm for the following assumptions:
+
+N is an integer within the range [1..100,000];
+each element of array A is an integer that can have one of the following values: 0, 1.
+https://app.codility.com/demo/results/trainingXWBP37-NDK/
+Time complexity: O(N)
+"""
+
+
+def solution(A):
+    east = 0
+    pairs = 0
+    for car in A:
+        if not bool(car):
+            east += 1
+        else:
+            pairs += east
+        if pairs > 1000000000:
+            return -1
+    return pairs
+
+
+s = solution([0, 1, 0, 1, 1])
+print(s)
