This function would be good if you know that all other integers are in the array once. However, this isn't elaborated within the question. A perfectly legal arr

This function would be good if you know that all other integers are in the array once. However, this isn't elaborated within the question. A perfectly legal array with the restrictions we've been given is this: [1, 3, 3, 9, 42] All numbers in the array are integers between 1 and 1,000,000, and one integer is in the array twice. As for the solution, allocate 1,000,000 bits and do a "bucket sort". If the next number in the array is n, check if the nth bit is 1. If it is, you've found the integer appearing twice. If the nth bit is 0, change it to 1 and continue.