# Optimal method to calculate 'p'

Given an array of length '$$n$$' with positive integers. Let's consider the sum:

$$S(p) = \sum_{i=p}^n \lfloor(\frac{a(i)}{i-p+1})\rfloor$$

where $$[...]$$ denotes the greatest integer function and $$p = 1,2,3...n$$. Now given an integer '$$m$$' find minimum '$$p$$' which satisfies $$S(p)\leq m$$ If no such '$$p$$' exists then output '$$-1$$'. The expected complexity should be $$n · max(\sqrt{a(i)})$$.

Any idea on how to solve it? I can find sum $$S(i)$$ where $$i = 1$$ to $$n$$ in $$n · max(\sqrt{a(i)}$$) but how to extract each $$S(i)$$ in $$O(1)$$ time? Also $$n\leq 10^5$$ and $$a(i)\leq10^5$$.

• Hi & welcome to MSE. I'm not clear on what you mean by "The expected complexity should be $n · \sqrt{a(i)}$". In particular, what value of $i$ to use in $a(i)$? I assume you mean you take some maximum value, say $M$, of all of the $a(i)$ values, i.e., $a(i) \le M$ (with this being $10^5$ in your case), with the complexity then being $n · \sqrt{M}$. Is this the case? Also, if so, this assumes you are checking the values of $a(i)$ in some way as, otherwise, it seems to me the complexity would be independent of $a(i)$ and just depend on $n$ instead? I suggest you explain this further. Thanks. – John Omielan Mar 4 at 3:29
• Yes , you are right M = max(a(i)) over all i's.I have changed it. Also please provide your algorithm which is independent of a(i).Thanks – Tourist_123 Mar 4 at 3:49
• The "algorithm" I'm considering is the basic, brute force method of calculating $S(i)$ for each each $i$ starting at $1$ until either you find a $p$ such that $S(p) \le m$ or you reach $i = n$. This complexity, I believe, is of $O(n^2$, so it's obviously not a particularly efficient or desirable procedure. I assume you have some other algorithm in mind by your statement. If so, it might help everyone here if you give a few details about it. Also, as for getting each $S(i)$ in $O(1)$ time, I don't see any way to do it, or even that it's possible. Do you know, or believe, such a method exists? – John Omielan Mar 4 at 4:06
• Thanks but I don't have one.I know how to calculate Sum S(i) , i=1 to n in n*sqrt(max(a(i)) using this link:- math.stackexchange.com/questions/926453/… .Also it is guaranteed that an algorithm will exist to determine 'p'. – Tourist_123 Mar 4 at 4:09