let the array be 3 1 2 1 3 4 first repeated integ…
Unknown - Mar 6, 2013
let the array be 3 1 2 1 3 4
first repeated integer is 3 here
start from the first and go till the end
add n+1 to the a[a[i]] where i is the current index.
iterate again dividing the values by n+1 if values comes 1 . the remainder is the repeated one.
We can find out the duplicate element by using Set, list or trvaersing using loop on array.
Below link can be useful to find out the algorithm to find duplicate or repeated elements in an array in java
Find out duplicate or repeated elements in an array in java
You said the array elements are all larger than 0. You never said we cannot modify the original array.
My way of solving this is:
A[6] = {3 1 2 1 3 4}
At index 0, mark A[abs(A[0])] = A[3] = -abs(A[3]) = -1
A[6] = {3 1 2 -1 3 4}
At index 1, mark A[abs(A[1])] = A[1] = -abs(A[1]) = -1
A[6] = {3 -1 2 -1 3 4}
At index 2, mark A[abs(A[2])] = A[2] = -abs(A[2]) = -2
A[6] = {3 -1 -2 -1 3 4}
At index 3, check A[abs(A[3])] = A[1] < 0.
At here we know some other index has value A[3]. Thus return abs(A[3]) = 1
If array has value 0, this method fails. If array element > array size -1, fail. If array has negative value, fail. But given the conditions you provided, the above algorithm works.