Have been working on the second constraint. My strategy was to first sort the input , and sort the radicals in place according to the increasing . With Python, I couldn't work around the in-place sorting quickly enough (thought of insertion sort, but without pointer it's hopeless).

Then I tried to use the radicals as hash keys, so we won't have to go through the smaller integers again and again (sorting is, after all, at best, which is a lot when we need to do this for every ). But with this kind of hashing, getting the target element is no longer , as we would have to iterate all the hash keys before we hit our target (that makes it I believe). Still not passing it on time.

By the way, I was generating all radicals till aiming for the first two constraints. I think we need to take another approach (iterating on radical and count its occurrences within the upper limit) for the last.