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

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