Check if in array contains duplicates in $O(1)$ space complexity and $ O(n)$ time complexity.
Examples:
Input: [1,2,3,1]
Output: true
Input: [1,2,3,4]
Output: false
Pretty straight forward question if space complexity can be more than $O(1)$.
How to do this in $O(1)$ space complexity and $O(n)$ time complexity. Bonus points for improving time complexity.
EDIT: Please don't use lookup tables like: boolean[INT_MAX] etc. I am looking for some sort of maths function which behaves in a certain way if input is repeated twice.
EDIT2: From comments below, I don't know if it can be done in the above constraints. I have this hunch that there may be a function which takes O(1) time and it's values changes in a certain way if input is repeated. Assume that array is positive integers only.
Note your question is basically the same as the StackOverflow one at Find duplicates in an array. You may be especially interested in the answer by amit (description says he's a software engineer at Google), who says
It also later says
When I first read your problem, I recalled even the best general-purpose sorting algorithms require $O(n\log n)$ time, so I assumed something similar would also be required here, with this helping to confirm my suspicion.
The rest of the answers there provide other possibly useful information for you, including where your requirements may hold in some very special cases.
There is not much more that I have to add to what is in that link. However, for whatever it's worth, here is other options I considered. One of them was that if you only allow a fairly limited set of positive integers, you can assign each positive integer to its corresponding prime index value (e.g., $1$ goes to $2$, $2$ goes to $3$, $3$ goes to $5$, $4$ goes to $7$, etc.). Then you keep a running product of the primes, starting at $1$. For each array value, you check if the corresponding prime divides the current product. If so, you have a duplicate & stop. Otherwise, you multiply the product by the corresponding prime & go to the next value. However, this can quickly bypass any integer size limits. Also, with some sort of unlimited integer size type handling, it generally will require more memory storage than just using bits, or even bytes, in an array to store whether or not a value is used.
Another option I considered is to do a type of hashing by choosing a fairly large integer $k \gt 1$, and then get the dividend & remainder for each array value. It'll keep track of the minimum & maximum dividends encountered for each possible remainder. Of course, the same value is already there when checking, they are duplicates, so the algorithm is then finished. Otherwise, it goes through the array again, checking for the next values larger than the previous minimum & smaller than the maximum. However, this may require going through the array many times, especially in worse case scenarios where the values mostly (or even all) have the same remainder.
As for your comment that this is a "general SDE interview question", my suspicion is they're likely not be looking for a specific solution. Instead, they're possibly checking what you know about this problem, as well as what sorts of things you may suggest in terms of solving it, including which restrictions you may suggest so it can be solved as requested. During my over 30 years of computer programming, I've encountered many problems which cannot reasonably be solved as well as I would like. Instead, I've needed to compromise & just do the best I can. This was especially the case when I began programming in the late 1970's and during the 1980's when computers were much less powerful than they are now.