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$.

  • $\begingroup$ 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. $\endgroup$ Mar 4, 2019 at 3:29
  • $\begingroup$ 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 $\endgroup$ Mar 4, 2019 at 3:49
  • $\begingroup$ 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? $\endgroup$ Mar 4, 2019 at 4:06
  • $\begingroup$ 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'. $\endgroup$ Mar 4, 2019 at 4:09


You must log in to answer this question.

Browse other questions tagged .