value duplication issue
-
The issue is: You are given an array of integers of size n containing values in the range 1 to n-1. Obviously there’s at least one duplicate value in this array. Please let me know the algorithm for finding one such duplicate value. Thanks.
Hint: sort the array.
"When I was born I was so surprised that I didn't talk for a year and a half." - Gracie Allen
-
The issue is: You are given an array of integers of size n containing values in the range 1 to n-1. Obviously there’s at least one duplicate value in this array. Please let me know the algorithm for finding one such duplicate value. Thanks.
Why is it obvious that there's atleast one duplicate value in this array?:) ARSALAN MALIK
-
Why is it obvious that there's atleast one duplicate value in this array?:) ARSALAN MALIK
-
The issue is: You are given an array of integers of size n containing values in the range 1 to n-1. Obviously there’s at least one duplicate value in this array. Please let me know the algorithm for finding one such duplicate value. Thanks.
If the array is sorted then use a binary search to check the value at each position against the value of the position : if ( a[i] == i+1 ) then the duplicate is in the section greater than i else the duplicate is in the section less than or equal to i. If the array isn't sorted then allocate a temp array of size n and walk through the original putting 'check marks' in the temp array at the appropriate index (value-1). As soon as you find a value that has alreay been 'checked' you have your duplicate. ...cmk Save the whales - collect the whole set