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