Getting a Different Number
Can you do this with Time O(N) and Space O(1)?
Given an array
arr of unique nonnegative integers, implement a function
getDifferentNumber that finds the smallest nonnegative integer that is NOT in the array.
Even if your programming language of choice doesn’t have that restriction (like Python), assume that the maximum value an integer can have is
MAX_INT = 2^31-1. So, for instance, the operation
MAX_INT + 1 would be undefined in our case.
Your algorithm should be efficient, both from a time and a space complexity perspectives.