Doubt in FLOORI4

It is mentioned in the editorial of this problem that there are only sqrt(n) different values for [n/i] over all i from 1 to n.

Can any one tell me that what is it true?

Link for the editorial :- FLOORI4 Editorial

Problem Link :- Problem

1 Like
This is because for i > √N, ⌊ N/i ⌋ < √N. Therefore for i = √N + 1 to N, it has only √N distinct values. And obviously for i from 1 to √N you can have √N different values. So actually the number of distinct values can be at max 2*√N.

Lemme know if this helps! :)
1 Like