arrays - 查找数组中对 (a, b) 的数量，使得 a % b = 0

Question

我得到了 O(N^2) 的解决方案，这是我的解决方案：

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

Answer 1

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)