Author, Tester & Editorialist: Hritik Seth
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.
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.