How to find it in O(sqrt(n)) ?
problem: https://www.spoj.com/problems/AE00/
solution(both O(n*sqrt(n)) & O(sqrt(n)): AlgoCode/AE00_Rectangles.cpp at master · hetp111/AlgoCode · GitHub
I didn’t understand the O(sqrt(n)) method. can someone explain?
Thank you.
Since you have to only count pairs where c <= d and c*d<=n, you know that c*c<=c*d ( from first relation, multiplying c on both sides ). So you must always have c*c <= c*d <= n, that is, c*c<=n. So c is bounded in the interval [0,sqrt(n)], hence you just iterate over all values of c and for a given c, you can find all possible values of d in O(1) time. So, total time complexity will be O(sqrt(n)).
for a given value of c how do i find all the possible values of d in O(1) ?
The formula is (n/c - c + 1) but i didn’t understand.
Let’s look at how to do it for a certain example.
Consider n = 50, then c*c<=50 implies c<=7 (since we are only interested in integers).
So, now
For c=1 we have c*d<=50 which means, d<=50, but you also need c<=d, so for c=1 you can only take d>=1,so there are 50 possible values of d when c=1. ( That is, from 1<=d<=50 ).
I’ll show explain two more cases,
For c=5 we have c*d<=50 which means, d<=10, so there are 10 possible values of d when c=5. (Here 50 is divisible by 5, so it is special). So, now you need to count d such that, 5<=d<=10, which gives you 6 values of d. ( Note, you have to include both 5 and 10 ).
For c=7 we have c*d<=50 which means, 7*d<=50, so the possible values of d when c=7 are when 7<=d<=7 , so there is only one possible value of d such that given conditions are satisfied.
In general, for a given c, since you have c*d<=n, it means that d<=floor(n/c) and you also have c<=d, so you have to count integers starting from c going till floor(n/c), which is (n/c) - c + 1. Note, here n/c directly gives you floor, since you are doing Integer division.
Thank you so much…!