CODEWITHSUNDEEP
c++time-complexity
Akshat Shrivastava
Akshat Shrivastava

Reputation: 73

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

I have an array of sorted (ascending order) elements as input. I want to find out whether these elements make a series in which each current element is divisible by all the elements that came before it. This is an obvious solution to this problem in O(n) time that I could think of:

bool CheckArray(int arr[], int no_of_elements)
{
    if (no_of_elements == 1)
        return true;

    for (int i = 1; i < no_of_elements; i++)
        if (arr[i] % arr[i - 1] != 0)
            return false;
    return true;
}

Example 1: Input: 3 6 9 12 Output: False

Example 2: Input: 3 6 12 Output: True

Is there any way to do it in less than O(n) time though? If yes, how?

Upvotes: 6

Views: 343

Answers (2)

Bathsheba
Bathsheba

Reputation: 234715

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.

Upvotes: 5

Jeffrey
Jeffrey

Reputation: 11410

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).

Upvotes: 6

Related Questions