Here is an interesting question that I found in a site. The catch is that it is not tricky C question, but a tricky math Q :)
There are numbers from
1 to N in an array. out of these, one of the number gets duplicated and
one is missing. The task is to write a program to find out the
duplicate number. Conditions: you have to do it in O(n) time without
using any auxilary space (array, bitsets, maps etc..).
#include <stdio.h>
int main()
{
int uiCount=0,uiSum=0,uiSqSum=0,i=0,uiSumDiff=0,uiSqSumDiff;
int uiNum;
int flag=0,uiTotal=0,uiN1=0,uiN2=0;
scanf("%d",&uiCount);
while(i++<uiCount)
{
scanf("%d",&uiNum);
uiSum+=uiNum;
uiSqSum+=uiNum*uiNum;
}
uiSumDiff=uiCount*(uiCount+1)/2-uiSum;
if(uiSumDiff<0){uiSumDiff*=-1;flag=1;}
uiSqSumDiff=uiCount*(uiCount+1)*(2*uiCount+1)/6-uiSqSum;
if(flag)uiSqSumDiff*=-1;
uiTotal=uiSqSumDiff/uiSumDiff;
uiN1=(uiTotal+uiSumDiff)/2;
uiN2=uiTotal-uiN1;
printf("The dulicate number is %d \n",(flag)?uiN1:uiN2);
return 0;
}