Find the number of distinct numbers in multiplication table

algorithm

Solution

The problem is that to use a set to verify the uniqueness, you have to populate it first, and it's O(n^2), one way or another; without a set, you can't easily verify if a number is unique or not...

As a side note: since big-O class is somewhat broad (i.e. it can describe any complexity not higher than something, but not necessarily not lower, ie. both linear complexity and quadratic complexity algorithms can be described as O(n^2), since, in both cases, the complexity is not higher than n^2) - as such, assume that every O(x) in this answer means "Big Theta", ie. asymptotical up/down boundary, such that f(n) is in O(g(n)) means that k1*g(n)<=f(n)<=k2*g(n) (k1,k2 positive of course).

As https://mathoverflow.net/questions/108912/number-of-elements-in-the-set-1-cdots-n-times-1-cdots-n?lq=1 points out, the exact amount is asymptotically approaching a well-known value; even so, the exact value for any given `n` is not something that can be calculated simply, as, in essence, it's quite similar to solving http://en.wikipedia.org/wiki/Prime-counting_function -

that said, let's try to summarize the facts, "(why?)" marking the fields I'm too lazy/tired to explain ATM, but which an interested reader may verify (or disprove) himself:

a) no well-known formula to get the result by a simple function a(n) currently exists,

b) because of that, we are required to generate a set with all of the unique numbers and return the cardinality of that set as the result,

c) since the amount of actual numbers in the set is proven to be o(n^2) (see the reference), strictly speaking o(n^2/(log n)^c * (loglog n)^3/2), generating the set would take at least that much operations - that's our low bound - assuming we already know if a number is in the set or not,

d) as such, complexity C of our algorithm A can be though, at best, to be such that

O(n^2) > O(C) > O(n^2/(log n)^c * (loglog n)^3/2) (please note that this represents only minuscule improvement over pure n^2).

That said, my proposition for A goes as follows:

a) since the matrix is symmetric vs the diagonal, assume we're analysing only e.g. upper right triangle plus diagonal

b) assume that, for your n, any number x =< n is in the set

c) calculate y=int(sqrt(n)) - every diagonal value of row r <= y is already present in the set, every diagonal value of row r > y has to be checked

c') n*(n+1)/2-n-int(sqrt(n)) elements need to be processed (added to set) in the "conventional" method

d) now, since we ruled out all the values that can be predicted easily, we enter the main loop: for (row r < n) // max number is r * n all x : x > (r-1) * n are guaranteed to be unique till now, so they needn't be processed, assuming we wouldn't have to maintain unique numbers set!; since the row's set is for numbers (r^2;r*n), all numbers in range ((r-1)n,rn) in row r are in range now, since the actual set of numbers in row r is a_n = r, 2*r, 3*r ... nr, the obvious problem is to find a "border" integer yr such that y*r > (r-1)*n, because that would mean that we have n-y guaranteed uniques. nb if we find an exact value of ((r-1)*n)/r to be an integer, we can safely assume that y = ((r-1)*n)/r + 1 (why?), and that exact integer is not unique. because of this, there is exactly max(n-r,ceil(n/r)) guaranteed uniques in every row (why?); we get this in O(1) for every row

e) the trickiest part: we've got some number >= than r*r, but obviously smaller than (r-1)n; that is the "hard range", [rr, (r-1)*n) , in which the number can be or not be unique; we can have at most i_r = max(0,n-r-floor(n/r)) numbers to check this range (why?) even naive checking every number in this range is obviously faster than O(n) (why? -floor(n/r) factor grows with respect to n !)

we already got better than O(n^2) - we have sum(i_r) iterations, for r = 2..n (first row is no-op), so this is actually equal to sum for r=2..n(max(0,n-r-floor(n/r))) - I won't provide an exact complexity class result here, as it's not a pretty number, Let's try to go even further...

f) What about a catapult?

g) For odd rows, we can't do much more (since this would, amongst many things, require us to solve some prime-related problems, already mentioned in the comments, which hasn't been solved for world's best matematicians yet) - yet we still can help ourselves for every even r!

divide r by two. every number that is <= r/2 * n has already been processed! it's either unique or not, we don't have to care!.

Note that since we actually dropped the ends of the rows already (and most of the beginnings too), this works surprisingly good. Since we do this check only on even rows, we just start checking them (adding to set) not from x = r*(r+1), but from r/2*n+r instead!

h) but now, the most important thing: how to check them if we don't have a set of already found uniques defined? sadly, this is the main problem with any algorithm that tries to go below ~n*n/2 element iterations - since you don't process all values, how can you know if the value has been processed or not?

i) if there was an easy way to predict how many (eg. %) of the "potentially unique" numbers are really unique, there won't be any real problem here, it would be a O(n) problem - but I simply consider it impossible, due to above difficulties.

tl;dr - I call shenanigans on any answer trying to do it strictly below O(n^2) - you can drop a few bits below, but the complexity class won't get reduced anyway.

Problem

Original source