Suppose we are given number N we have to find a number M less than N such that M*M when divided by N gives maximum remainder .↵
Also value of M should be maximum possible ( nearest to N).↵
↵
↵
------------------↵
↵
It is given that all computed values are within integer range.↵
for e.g :↵
N=15↵
↵
maximum remainder is obtained from M=5 and M=10↵
↵
so M = 10 is the answer. ↵
↵
------------------↵
↵
I could only formulate the naive solution for it which works in O(N) time complexity.↵
Any better approach for this ??↵
Also value of M should be maximum possible ( nearest to N).↵
↵
↵
------------------↵
↵
It is given that all computed values are within integer range.↵
for e.g :↵
N=15↵
↵
maximum remainder is obtained from M=5 and M=10↵
↵
so M = 10 is the answer. ↵
↵
------------------↵
↵
I could only formulate the naive solution for it which works in O(N) time complexity.↵
Any better approach for this ??↵