0

I am getting the solution in O(N^2) here is my solution:

arr = [4,6,5,5,7,7,8]

count = 0

for i in range(n):

    for j in range(n):
        if (i!=j and arr[i]%arr[j]==0):
            count = count + 1
return count
2
  • Welcome to StackOverflow, Satvik! Can you please state your question in the post? As it currently stands, it looks more like a statement than a question.
    – Al.G.
    Dec 8, 2019 at 9:57
  • @satvik bansal Please specify what do you want to achieve. You want to reduce the time complexity? Dec 8, 2019 at 11:13

1 Answer 1

0

You have to check each item against another item, so the general code will be O(n^2).

You might be able to make it more efficient with knowledge of the structure of the problem.

For example if you have repeated values you can create a unique list first: this can have complexity O(n).

It might also be worth sorting the list so that you only divide larger numbers by smaller, but sorting is at worst O(n^2) anyway averaging at O(n log n).

You might be able to use clever mathematical properties depending on the number ranges to exclude a large part of the search (if the data has been sorted)

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.