A Small DoubtNeed Help on Modular Arithmetic question
Difference between en1 and en2, changed 41 character(s)
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 ??↵

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en2 English ankurrathinsit 2020-05-03 03:52:42 41
en1 English ankurrathinsit 2020-05-03 03:45:04 533 Initial revision (published)