Skip to content

Navigation Menu

Sign in
Appearance settings

Search code, repositories, users, issues, pull requests...

Provide feedback

We read every piece of feedback, and take your input very seriously.

Saved searches

Use saved searches to filter your results more quickly
Sign up
Appearance settings

Commit 6207f3b

Browse files
Add solutions for problems missing_integer, passing_cars
1 parent 2896924 commit 6207f3b

File tree

2 files changed

+93
-0
lines changed

2 files changed

+93
-0
lines changed
Lines changed: 34 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,34 @@
1+
"""
2+
Write a function:
3+
4+
def solution(A)
5+
6+
that, given an array A of N integers, returns the smallest positive integer (greater than 0) that does not occur in A.
7+
8+
For example, given A = [1, 3, 6, 4, 1, 2], the function should return 5.
9+
10+
Given A = [1, 2, 3], the function should return 4.
11+
12+
Given A = [−1, −3], the function should return 1.
13+
14+
Write an efficient algorithm for the following assumptions:
15+
16+
N is an integer within the range [1..100,000];
17+
each element of array A is an integer within the range [−1,000,000..1,000,000].
18+
https://app.codility.com/demo/results/training3KJDHP-5MC/
19+
Time complexity: O(N) or O(N * log(N))
20+
"""
21+
22+
23+
def solution(A):
24+
missing = 1
25+
for elem in sorted(A):
26+
if elem == missing:
27+
missing += 1
28+
if elem > missing:
29+
break
30+
return missing
31+
32+
33+
s = solution([1, 3, 6, 4, 1, 2])
34+
print(s)

‎5-prefix_sums/passing_cars.py‎

Lines changed: 59 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,59 @@
1+
"""
2+
A non-empty array A consisting of N integers is given. The consecutive elements of array A represent consecutive cars on a road.
3+
4+
Array A contains only 0s and/or 1s:
5+
6+
0 represents a car traveling east,
7+
1 represents a car traveling west.
8+
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.
9+
10+
For example, consider array A such that:
11+
12+
A[0] = 0
13+
A[1] = 1
14+
A[2] = 0
15+
A[3] = 1
16+
A[4] = 1
17+
We have five pairs of passing cars: (0, 1), (0, 3), (0, 4), (2, 3), (2, 4).
18+
19+
Write a function:
20+
21+
def solution(A)
22+
23+
that, given a non-empty array A of N integers, returns the number of pairs of passing cars.
24+
25+
The function should return −1 if the number of pairs of passing cars exceeds 1,000,000,000.
26+
27+
For example, given:
28+
29+
A[0] = 0
30+
A[1] = 1
31+
A[2] = 0
32+
A[3] = 1
33+
A[4] = 1
34+
the function should return 5, as explained above.
35+
36+
Write an efficient algorithm for the following assumptions:
37+
38+
N is an integer within the range [1..100,000];
39+
each element of array A is an integer that can have one of the following values: 0, 1.
40+
https://app.codility.com/demo/results/trainingXWBP37-NDK/
41+
Time complexity: O(N)
42+
"""
43+
44+
45+
def solution(A):
46+
east = 0
47+
pairs = 0
48+
for car in A:
49+
if not bool(car):
50+
east += 1
51+
else:
52+
pairs += east
53+
if pairs > 1000000000:
54+
return -1
55+
return pairs
56+
57+
58+
s = solution([0, 1, 0, 1, 1])
59+
print(s)

0 commit comments

Comments
(0)

AltStyle によって変換されたページ (->オリジナル) /