Sunday, July 8, 2007

Finding a duplicated integer problem.

Given an array of n integers from 1 to n with one integer repeated..

Here is the simplest of C programs (kind of dumb)


#include < stdio.h >
#include < stdlib.h >
#include < conio.h >

int i,j=0,k,a1[10];

main()
{
printf("Enter the array of numbers between 1 and 100(you can repeat the numbers):");
for(i=0;i <= 9;i++)
{
scanf("%d",&a1[i]);
}

while(j < 10)
{
for(k=0;k < 10;k++)
{
if(a1[j]==a1[k] && j!=k)
{
printf("Duplicate found!");
printf("The duplicate is %d\n",a1[j]);
getch();
}
}
j=j+1;
}

getch();
return(0);
}

6 comments:

Anonymous said...

sum of 1 to n = n(n+1) /2

duplicate number = (sum of array - sum of 1 to n)

Anonymous said...

YOu need to modify this to
duplicate number= total_no- (sumof 1 to n -sum of array).

This would give the correct result

Madan said...

what is "total_no"?
duplicate number = (sum of array - sum of 1 to n) is only correct

Gangadhar Mylapuram said...

The above solutions are wrong.
This can be solved in o(n) using two mathematical equations

SU= Sum of given elements;
ASU= Actual sum of 1-n integers

MU = Multiplication of given numbers
AMU = Multiplication of 1-n integers

R= Repeated number
M= Missing number
SU-R+M=ASU
MU * M/R = AMU

Substitute the values of SU,ASU,MU,AMU and solve the equations. You will get the answers.

Unknown said...

Thanks for the info. It is very helpful.
Regards
students area
Get jobs info at students area

Anonymous said...

Great weblog right here! Also your website a lot up very fast!
What web host are you the use of? Can I am getting your affiliate link in
your host? I desire my web site loaded up as quickly as yours
lol

Also visit my page; bmr calculator to lose weight