How to solve this in less than O(N)?

It is not possible to do it in better than O(n).

Each element could have a value that changes the solution from true to false. So, you need to do at least an operation on each element, to check it.

As such you'll have at least O(n).

Clearly you need an O(N) traversal in order to yield true.

The optimisation you can make is to yield a false as soon as possible.

I conject (and think the proof would be hard but is true if the numbers are arithmetically distributed) that adjacent larger number pairs (a, b) are less likely to be of the form (a, na) for integral n than smaller numbers. Therefore you could yield a false more quickly by considering the larger numbers first. In other words, running the loop from the last to the first element may well end up being statistically quicker. You'd have to profile on the typical number series that are presented to your function.

By the way, your preamble

if (no_of_elements == 1)
    return true;

is redundant.