Hewlett Packard Interview Question
Software Engineer / DevelopersCountry: India
Interview Type: In-Person
int FindRepeated (int *a, int n) {
int Repeated= 0;
for (int i = 0; i < n; i++) {
Repeated= Repeated ^ a[i];
Repeated = Repeated ^ (i+1);
}
// Repeated = 1 ^ 2 ^ ... ^ n ^ a[0] ^ a[1] ^ ...^ a[n-1]
return Repeated;
}
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;
@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.
i think it should be sum-(1+99)*99/2
- hasinamjanu September 18, 2011