Diving into the technical round, I was presented with a tricky problem about finding a duplicate number in an array. Right away, I felt the pressure, as it had to be solved with O(1) space and better than O(n^2) time. The funny part is that I had literally seen this exact question on prachub.com while preparing just days before.

The interview also included behavioral questions about teamwork and problem-solving. Overall, it was challenging, but I got the offer in the end, though I decided to decline.

Given an array of $n+1$ integers where each integer is in the range $[1, n]$, find the duplicate number. You must solve it without modifying the array and using $O(1)$ extra space. The time complexity should be better than $O(n^2)$.