You are given N disks and two rods, each with one initial disk.
On the left rod, disks can be placed in decreasing order of size (smaller disks on top of bigger ones). On the right rod, disks can be placed in increasing order of size (bigger disks on top of smaller ones). Note that it is not permissible to place two disks of equal size on top of each other. The initial disks cannot be moved.
Write a function:
def solution(A, L, R)
that, given an array A of integers representing the sizes of the N disks and two integers L and R representing the size of the initial disks on the left and right rods respectively, returns the maximum number of disks from A that can be placed on the rods while satisfying the rules presented above.
Examples:
1. Given A = [2, 3, 3, 4], L = 3 and R = 1, your function should return 3, since only three disks can be placed on the rods. Note that the disk of size 2 can be placed on either the left rod or the right rod.
2. Given A = [1, 4, 5, 5], L = 6 and R = 4, your function should return 4.
3. Given A = [5, 2, 5, 2], L = 8 and R = 1, your function should return 4.
4. Given A = [1, 5, 5], L = 2 and R = 4, your function should return 2.
Write an efficient algorithm for the following assumptions:
- N is an integer within the range [1..50,000];
- each element of array A is an integer within the range [1..1,000,000,000];
- L and R are integers within the range [1..1,000,000,000].
# you can write to stdout for debugging purposes, e.g.
# print("this is a debug message")
def solution(A, L, R):
# write your code in Python 3.6
N = 0
set_A = set(A)
B = list(set_A)
B.sort()
for L_candidate in B:
if L_candidate >= L:
break
A.remove(L_candidate)
N += 1
set_A = set(A)
B = list(set_A)
B.sort(reverse=True)
for R_candidate in B:
if R_candidate <= R:
break
N += 1
# you can write to stdout for debugging purposes, e.g.
# print("this is a debug message")
def solution(A, L, R):
# write your code in Python 3.6
N = 0
set_A = set(A)
B = list(set_A)
B.sort()
for L_candidate in B:
if L_candidate >= L:
break
A.remove(L_candidate)
N += 1
set_A = set(A)
B = list(set_A)
B.sort(reverse=True)
for R_candidate in B:
if R_candidate <= R:
break
N += 1
return N
# you can write to stdout for debugging purposes, e.g.
# print("this is a debug message")
def solution(A, L, R):
# write your code in Python 3.6
N = 0
set_A = set(A)
B = list(set_A)
B.sort()
for L_candidate in B:
if L_candidate >= L:
break
A.remove(L_candidate)
N += 1
set_A = set(A)
B = list(set_A)
B.sort(reverse=True)
for R_candidate in B:
if R_candidate <= R:
break
N += 1
return N
# you can write to stdout for debugging purposes, e.g.
# print("this is a debug message")
def solution(A, L, R):
# write your code in Python 3.6
N = 0
set_A = set(A)
B = list(set_A)
B.sort()
for L_candidate in B:
if L_candidate >= L:
break
A.remove(L_candidate)
N += 1
set_A = set(A)
B = list(set_A)
B.sort(reverse=True)
for R_candidate in B:
if R_candidate <= R:
break
N += 1
return N
# you can write to stdout for debugging purposes, e.g.
# print("this is a debug message")
def solution(A, L, R):
# write your code in Python 3.6
N = 0
set_A = set(A)
B = list(set_A)
B.sort()
for L_candidate in B:
if L_candidate >= L:
break
A.remove(L_candidate)
N += 1
set_A = set(A)
B = list(set_A)
B.sort(reverse=True)
for R_candidate in B:
if R_candidate <= R:
break
N += 1
return N
The following issues have been detected: timeout errors.
Small random tests, every value occurs at least twice. N = 100.
Medium random tests. N = 10,000.
running time: 0.456 sec., time limit: 0.208 sec.