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 ?
courtesy: Vibhaj
Click here to see the solution.
p.s. - For Remarks please hit the given link once. For Hint, hit it twice and for the solution, hit it thrice.
Hints: No hint this time. Hit again for solution. |
|
Solution:
For integers use sum to find the repeated number.
For floating numbers, use Hash tables.
Complexity:
1. Space: O(1) [O(K), K >> N for hash table]
2. Time: O(N)
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;
}
|
|
|
Posts
