# MRTRAVEL - Editorial

Author, Tester & Editorialist: Hritik Seth

EASY

# PROBLEM:

https://www.codechef.com/problems/MRTRAVEL

# EXPLANATION:

The Basic Approach for this problem was to find the number divisible by the element starting from minimum element and remove the element and it’s divisible number. So the number of times you remove the minimum element is the number of Bus passes required.

This approach would take O(n^2) time at worst and works for the problem.

# SOLUTIONS:

Editorialist's Solution
``````n = int(input())
cities = list(map(int, input().split()))
cities.sort()
passes = 0
for i in range(n):
if cities[i] == 0:
continue
passes += 1
t = cities[i]
cities[i] = 0
for j in range(i + 1, n):
if cities[j] % t == 0:
cities[j] = 0
print(passes)
``````

Well this was my approach, feel free to share your approach here. Suggestions are always welcomed.

2 Likes

Looking at the constraints of this problem, I think O(n^2) should not work(which is working). If I was a contestant I would try it in O(nlogn) or O(nsqrt(n)) looking at the constraints and be upset after contest that we can solve it in O(n^2).

Collectively, I am saying that Constraints should show the traits of what maximum expected complexity should be. Peace.