Such a clever solution! Thanks!

The following solution passed as well.

I tried n<=3, ans=1 n<=8, ans=2 n=9, ans=3So I guess, every 2x+1 the ans will increase by 1. So sum_{1,k} (2x+1) >= n => k >= -1 + sqrt(1+n)

This happens to pass all the tests here. Do not have time to verify this yet though...