Sarin

• Dec 24th, 2006

 

The solution is a bit long. You have to use sum of N and sum of N squares. Using this derive p-q=K1, p^2-q^=k2 kind of equations and then solve for p&q. The program that I wrote can be found at http://suseelan.googlepages.com/duplicateinsequence

vipin gupta

 Profile Answers by vipin gupta Questions by vipin gupta

• Dec 26th, 2006

 

Thanks for the great solution. The Only problem with it is: it will find out the missing number rather than the duplicate number.
Anyways, its the solution I was looking for.
Regards

manoj

• Dec 27th, 2006

 

thanks for the cool problem and a cool solution. once we have the missing number, we can easily find the duplicate number once we have the missing number (from above prog) using - sigma(x) - (n(n-1)/2 - m)CMIIW, -Manoj

shivakumara.madegowda

 Profile Answers by shivakumara.madegowda 

• Jan 6th, 2007

 

#define MAX 5
main(){
        int a[MAX]={1,2,3,1,5};
        int num=1, i=0, missed=0, duplicated=0;
        while(num <= MAX ){
                if(num != a[num-1]){
                        missed=num;
                        duplicated=a[num-1];
                }
                num++;
        }
        if(missed && duplicated)
                printf("Missed number is %dn Duplicated number is %dn", missed, duplicated);
}

Visitor

• Jan 13th, 2007

 

The problem of the following algorithm: you can't assume that the numbers are sorted except the duplicated one.

#define MAX 5
main(){
        int a[MAX]={1,2,3,1,5};
        int num=1, i=0, missed=0, duplicated=0;
        while(num <= MAX ){
                if(num != a[num-1]){
                        missed=num;
                        duplicated=a[num-1];
                }
                num++;
        }
        if(missed && duplicated)
                printf("Missed number is %dn Duplicated number is %dn", missed, duplicated);
}

Bala

• Feb 8th, 2007

 

The coolest solution I have seen, good use of math :-))

Balaji

• Feb 8th, 2007

 

Solution will give both duplicate and missing number, if number in the sequence is greater N1 duplicate N2 missing, else N1 is the missing and N2 the duplicate



cheers

Bala

Visitor

• Feb 20th, 2007

 

#include <stdio.h>
int main(void)
{
 int totalNum, realNum, missNum, dupeNum;
 int i=1, realSum=0, realSqSum=0, idealSum=0, idealSqSum=0, diffSum=0, diffSqSum=0;
 printf("We want to SUM(1+2+3...+N)n");
 printf("Input the last number N:");
 scanf("%d",&totalNum);
 
 printf("Be caureful about that.n");
 printf("One of the number duplicate and so one is missing.n");
 printf("Input the sequence number which you want.n");

 while ( i <= totalNum )
 {
  scanf("%d",&realNum);
  realSum+=realNum;
  realSqSum+=realNum*realNum;
  i++;
 }

 idealSum=(totalNum)*(totalNum+1)/2;
 idealSqSum=(totalNum)*(totalNum+1)*(2*totalNum+1)/6;

 diffSum=idealSum-realSum;
 diffSqSum=idealSqSum-realSqSum;
 missNum = (diffSum + (diffSqSum/diffSum))/2;
 dupeNum = missNum - diffSum;
 
 printf("Duplicate Number is %d, and missing number is %dn",dupeNum,missNum);
 return 0;
}

sumit.manchanda

• Mar 2nd, 2007

 

say we have a sequence
3,2,1,3,5 now missing no= 4, duplicated =3
 now we know 1+2+3+4+.......n =n*(n+1)/2
& 1^2 +2^2+3^2+ ..... n^2 =n*(n+1)(2n+1)/6

let missing no = p && duplicated n0 =q
 now 1+2+3+4+5= (5*6)/2= 15
& sum of given sequence would be

3+2+1+3+5 =14

now p-q= n*(n+1)/2 - sum of given sequence
        =  15- 14
        =  1
1^2 +2^2+3^2+4^2+5^2 =55== (5*(5+1)*(2*5+1))/6
 now sum of squares of given sequence=
3^2+2^2+1^2+3^2+5^2= 48

now
sum of squares of no from 1 to n - ( sum of squres of no given sequence)= 55 - 48= 7
p^2 - q^2 = is also 7
 hence we have  p^2 - q^2 = (p-q)*(p+q)
p-q we already have from our previous calculation
we can find p+q

now solving for p & q from eq p-q=1
& p+q =7
we get p= 4 & q = 3
now program can be easily made with this concept
here complexity would be O(n)as

ti_abhi

 Profile Answers by ti_abhi 

• Mar 14th, 2007

 

This can't get any easier than this:

1. Assuming list is sorted
    a. Run a FOR loop. Take the difference of consecutive numbers ,starting from the greatest. (N)
    b. If the difference between consecutive numbers is '0', thats the repeated number. This may take less than or equal to O(N) times.
    c. Use the following equation as mentioned by someone in this forum:
             Mysum - D + M = Realsum
    Mysum is known, Realsum is known, duplicate number has been found. so find 'M'. Kind job right? ;-)

2. Assuming list is not sorted.
    a. Run 2 for loops, one containing starting half of array and another containing last half of array. compare values to find the duplicate.
    b. use b and c above to do the rest!!

Siddharth

• Oct 13th, 2017

 

Here is the code

Code
#include<stdio.h>


#include<stdlib.h>


 


void printTwoElements(int arr[], int size)


{


    int i;


    printf("


 The repeating element is");


 


    for(i = 0; i < size; i++)


    {


        if(arr[abs(arr[i])-1] > 0)


            arr[abs(arr[i])-1] = -arr[abs(arr[i])-1];


        else


            printf(" %d ", abs(arr[i]));


    }


 


    printf("


and the missing element is ");


    for(i=0; i<size; i++)


    {


        if(arr[i]>0)


            printf("%d",i+1);


    }


}


 


/* Driver program to test above function */


int main()


{


    int arr[] = {7, 3, 4, 5, 5, 6, 2};


    int  n = sizeof(arr)/sizeof(arr[0]);


    printTwoElements(arr, n);


    return 0;


}