How many distinct values of floor(N/i) exists for i=1 to N. Say we have a function $F(i)=\text{floor}(N/i)$.
Then how many distinct values of $F(i)$ will exist for all $0 \leq i \leq N$
e.g. We have $N=25$ then.
$F(1)=25$
$F(2)=12$
$F(3)=8$
$F(4)=6$
$F(5)=5$
...
...
...
$F(24)=1$
$F(25)=1$
So total distinct values of $F(i)$ are $(N=25)$ :- $25, 12, 8, 6, 5, 4, 3, 2, 1$
total distinct values are $9$: $(2 \times 5-1)$
Can anyone please help in that total number of distinct values are $O(\sqrt{N})$?
 A: Let $k = \left\lfloor{\frac{N}{i}}\right\rfloor$. Take two cases -


*

*$k \le \sqrt{N}$: Clearly there are $\mathcal{O}(\sqrt{N})$ possible values for $k$ in this case

*$k > \sqrt{N}$: In this case $i \le \sqrt{N}$. Since there are $\mathcal{O}(\sqrt{N})$ possible values for $i$, there are $\mathcal{O}(\sqrt{N})$ values for $k$ as well.


$\implies$ the maximum distinct values of $k$ is $\mathcal{O}(\sqrt{N})$
A: If $k \leqslant \sqrt{N}$, then $\lfloor N/\lfloor N/k\rfloor\rfloor = k$, since, letting $m = \lfloor N/k\rfloor$, we have $$mk\leqslant N < (m+1)k = mk + k \leqslant mk + m = m(k+1),$$ so that gives you $\lfloor \sqrt{N}\rfloor$ values. And the values of $\lfloor N/k\rfloor$ for $k \leqslant \lfloor \sqrt{N}\rfloor$ are all different, since
$$\frac{N}{k-1} - \frac{N}{k} = \frac{N}{k(k-1)} > 1$$
for $1 < k \leqslant \lfloor \sqrt{N}\rfloor$.
So you have either $2\lfloor \sqrt{N}\rfloor$ or $2\lfloor\sqrt{N}\rfloor - 1$ distinct values, depending on whether
$$N \geqslant \lfloor \sqrt{N}\rfloor(\lfloor\sqrt{N}\rfloor+1)$$
or not.
A: Get the ceil() value of the positive root of the equation t^2 + t - (N + 1) = 0.
Let's say the required root be r, then compare (r^2 - 1) with N if (r^2 - 1 >= N)
the answer will be 2 * ( r - 1) else the answer will be 2 * (r - 1) + 1.
Here is cpp psuedo code :
    int n; // get n
    int r = ceil((sqrt(5 + 4 * n) - 1.00) / 2.00);
    if(r * r - 1 >= n)
        return 2 * (r - 1);
    else
        return 2 * (r - 1) + 1;  

