CareerCup

i think it should be sum-(1+99)*99/2

XOR all numbers in the array and all numbers from 1 to 99.

Here is one of the correct solution

int FindMyRepeat(int* a, int n)
{
	int actualSum = (n*(n+1))/2;
	int actualProd = 1;
	int realSum = 0;
	int realProd = 1;
	for(int i=1;i<=n;i++)
	{
		actualProd = actualProd*i;
		realSum = realSum + a[i-1];
		realProd = realProd*a[i-1];
	}
	int diff_sum = actualSum - realSum;
	printf("Diff = %d\n",diff_sum);
	printf("ActualProd = %d\n",actualProd);
	printf("RealProd = %d\n",realProd);
	int repeat = (diff_sum * realProd)/(actualProd-realProd);
	return repeat;
}

int cntSum = 0;  //this will keep the sum from 1 .. 99
int arrSum = 0; //this will keep the array sum
for(int i = 0; i<100 ;i++)
{
  arrSum += arr[i];
  if(i != 99)
   cntSum += i+1;
}
 cout<<"Repeated element: " <<arrSum - cntSum<<endl;

//The sum of numbers from 1..99 = 99*(100/2) = 4950

int arrSum = 0;
for(int i = 0; i<100 ;i++)
{
arrSum += arr[i];
}
cout<<"Repeated element: " <<arrSum - 4950<<endl;

@Ayad:This is nt working dude....check if array size 5...i.e n=5.....and array elements are 1 2 2 3 4..it should return 2....but according 2 ur logic it returns 3.

@hasinamjanu: u really need to work out ur maths. Ayad solution will work absolutely fine. for array of size 5, n will be equal to 4 and not 5.

@Test: Xoring doesn't require the numbers to be in order. the example you took is wrong.in your example you missed the number 4. the elements should be 1, 2, 3,3,4,5.

Finding the repeated number is not an issue. more importantly finding its index efficiently is an issue.

even index also can be found...but for this case we have to use an array..space complexity will be 0(n).

Not exactly. Once we find the duplicate number then we just need to search it in the array. linear search will do the work in O(n) time and no extra space.

Classic interview question, XOR solution.
stackoverflow.com/questions/2605766/how-to-find-a-duplicate-element-in-an-array-of-shuffled-consecutive-integers

what about finding the number of clears in an integer array.
For eg: if array is 1 -3 4 2 3 5... -3 and 3 is one clear.. how to count the number of clears like this.

int a,b[100]; //fill in values b[100]
sum=0;
int num;
a=(99(99+1))/2
int i=0;
for(i=0;i<100;i++)
{
sum=sum+b[i];
}
num=sum-a;
printf("the repeated number is %d", num);

(1+99)*99/2-sum

yes it is sum-(1+99)*99/2

but we cant find the index of the element.

if we need Index of the element then we should to bindery search.

XOR all numbers in the array and all numbers from 1 to 99.

@Arja: A XOR A = 0, and
A XOR A XOR A = A
therefore XORing all the elements and 1 to 99 only leaves the repeated number