Find repeated element

Given an array of size N which contains all the numbers from 1 to N-1. Find the number which is repeated in O(N) time.
How do you proceed with the same with floating numbers from 0 to 1 instead of 1 to N-1 ?

Solution :

For integers use sum to find the repeated number.
For floating numbers, use Hash tables.

Complexity :

• Time : O(N)
• Space : O(1) [O(K), K >> N for hash table]

Code :

int repetition_int(int input[], int N){

int i=0, sum=0;

for(i=0; i<N; i++)

sum += input[i];

return sum - (N*(N-1)/2);

}

float repetition_float(float input[], int N){

int i;

for(i=0; i<N; i++){

if(hash_table_exists(input[i]))

return input[i];

hash_table_insert(input[i]);

}

return -1.0;

}