Getting a Different Number
2 min readNov 6, 2021
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.
