Can I modify the array?

Question

like putting interger into the i-th element of the array

Comments

Can you explain you solution? I can't think of a way to modify the array and reach the solution. Thanks :)

---

I think it is the only way to satisfy the O(n) time and O(1) space requirement. Observed that for a size n array, it can store only values 1..n. If are these elements are present, then next positive is n+1. Otherwise, if we put the things into the "right" place in the array, then the missing element will not be in place. So you can scan the array and see if A[i] == i+1. return i+1 if not, or return n+1 if no such i exist.

Answer 1

That's the only I've found to respect the complexity requirements.

Answer 2

Of course you can, but just for this problem. It is not a good style to change the source data in a project.