[sharth]

The second problem would be clearer if we knew how much scratch space we had. Is it zero? Is it O(1)? Is it O(n)?

[kspiteri]

You just need a constant number of pointers. This requires O(log n) scratch space because a pointer can be stored in O(log n) space.

[to3m]

Not if N=1 ;)

(A constant amount is of course independent of N anyway!)

[jgrahamc]

Can be solved with no extra storage just three ints or pointers.