CODEWITHSUNDEEP
algorithmmathtime-complexitymathematical-optimizationdiscrete-mathematics
user760900
user760900

Reputation: 606

How to approach optimizing algorithm with discrete

I came across this answer who said there is a "fancy discrete maths to do it faster" than O(n^2). I cannot understand how the question linked can be done in under O(n^2).

How would I approach this problem with discrete to try and understand a faster solution?

Task description:

Find the number of "lucky triples" in a list. "Lucky triple" is defined as "In a list lst, for any combination of triple like (lst[i], lst[j], lst[k]) where i < j < k, where lst[i] divides lst[j] and lst[j] divides lst[k].

Upvotes: 3

Views: 154

Answers (1)

גלעד ברקן
גלעד ברקן

Reputation: 23945

It seems that we have insufficient information to answer since the answer also depends on m, the maximum element in the list. Two ways it could be done faster than O(n^2) are if n^2 > n * sqrt(m) or n^2 > m * log(m) + n * log(m).

In the first case, we can iterate over each of lst[i]s divisors with a direct enumeration, taking time O(sqrt(lst[i])), and look up how many of them have been seen, who's count of seen divisors has already been recorded. (The number of divisors is constant for our discussion since it's size compared to m and n under our conditions is negligible.) For example,

2 8 5 16

2  -> nothing to do
8  -> divisors 2 4
      record {8: 1 divisor seen}
5  -> no divisors seen
16 -> divisors 2 4 8
      found 8 with 1 count in our record
      
Total 1 triple

In the second method, we precalculate the smallest prime factor for each number from 2 up to m, so as to enable us to factor each list element in O(log lst[i]). We then need an extra step to generate the divisors (the number of which we can again consider constant under our conditions) and perform a similar traversal as the first. This method could help if n is extraordinarily large, so as to still benefit despite the additional m log m cost.

Upvotes: 2

Related Questions