Duplicate in sequence
 

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;
}