Array searching problem?

Question

I have an infinitely long array. It has random numbers in it. For every number but one there is another number in the array. That is every number has a copy of itself in the array and there is only one number which is alone. how will you find this number?

Wanted the answer ASAP.
Thanks and Regards.

Answer 1

An interesting question. Are you allowed to take infinite time to solve it?



Because I'm not sure you can do this in a finite amount of time. If the array is not structured in any way, the only way you can determine that a number does not have a duplicate is to check it against every other element in the array. That's an O(n) process, and therefore can't be completed in finite time on an infinite array. Plus, you have to do this for each element in the array, which is another O(n) process.



amit's solution makes sense, but you can't sort an unsorted infinitely long array in a finite amount of time, unless you have an O(1) sorting algorithm.



However, I'm so sleep-deprived at the moment that I may not be thinking about this correctly. So this answer may be complete balls. I'd be interested to see what you come up with.

Answer 2

take your same array list in two array variables. get one array list sorted in any order. then pick first element from the unsorted list and match with the each and every element of the sorted list if a match is found count it.. i think you will got an idea now..

Answer 3

Assume a as an integer array

int i,j,k=0;

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

flag=0;

for(j=0;j<5;j++){

if(a[i]==a[j]&&i!=j)

flag=1;

}

if(flag==0){

b[k]=a[i];

K++;

}

}



P.s array b contains the unique elements in an array.

typed this from handset , sorry for any syntax errors.

Answer 4

Create a boolean variable that tracks despite in case you have already revealed "errors". on the precise of your software declare the bool: bool bPrintedError = fake; The, around the printf fact, do this: if (!bPrintedError) { printf("Errorn"); bPrintedError = genuine; }