dmag

• Aug 3rd, 2006

 

You can use the Sn = n/2(n+1) to figure out the summation of 1,2,....,n numbers and using a for loop add the values of the given array. and difference between these two gives the result desired. Sometimes you want to take the absolute value of this difference.

vipin gupta

 Profile Answers by vipin gupta Questions by vipin gupta

• Oct 17th, 2006

 

we can try this:
1. Take a newarray of size N. Initialize every element of this array to 0.
2. for(i = 1; i <= N; i++)
{
newarray[i] = newarray[i] + 1;
}
3. find j in newarray, such that, newarray[j] > 1. Find k in newarray, such that, newarray[k] = 0.
4. j is the element which is repeated twice & k is the element which is missing.
I hope I am clear

siriradha

 Profile 

• Oct 17th, 2006

 

This Code as worked.Insteadof giving specific numbers u can give N natural numbers as inputs as specified in the question,u can use the same concept of for loop .U will the result

Module Module1

sub Main()

 Dim arr() as Integer={1,2,3,4,6,6,8}

for i as integer =1 to 8

if arr(i)=arr(i+1) then

console.writeline("Missing number is "&(arr(i+1)+1))

exit for

end if

next i

end sub

end module

vasu

• Oct 31st, 2006

 

1. establish an array a[100].
2. initialize i,j
3. repeat until i<n

a)compare two adjacent element a[i]<>a[i+1] if first element is equal to second then assign location where duplicate occurs to  j=i+1.

and update a[i+1] by a[i]+1

Shiva

• Nov 2nd, 2006

 

How about 5. The program doesnt print for 5. Check for difference between a[i+1] -a[i] if it is 1 the number is present. If it is 0 or 2 then a[i] +1 is missing. cases: 1 2 3 4 5 5 7 a[i+1] - a[i] =0 at i =5 so 6 is missing 1 2 3 4 6 6 7 a[i+1] -a[i] = 2 at i =4 so 5 is missing.

mohammed riyaz

• Apr 24th, 2007

 

if the series is like n() = {1,2,6,4,5,6,7,8,9}this logic will not work

Gaurav

• Jun 7th, 2007

 

As the problem himself states that an array is having integers from 1 to N, so in case the array is a sorted array then simple we can find the duplicate and Missing number by

using For loop

for(i=0;i{
  if( a[i] != (i+1))

  {
     print("the Missing number is %d and duplicate number is %d", (i+1), a[i]);
    break;
   }

}

I think it will work, try for some problem

neverd

 Profile Answers by neverd 

• Jun 8th, 2007

 

I think the question includes the case like following
int arr[5]  = { 1, 3, 2, 3, 5}
in this case,
4 is missing
3 is duplicate

drmfslx

• Aug 10th, 2007

 

Method 1: (works for any array of integer, not necessarily for 1-N)
1. Sort the array using counting sort which takes O(N).
2. A for look to search the missing one and the repeated one which also takes O(N)
 int cur = 0;
 for( int i=0; i<N; ++i )
{
    if( inputArray[i] > ++cur )
        ;// find the missing one
    else if( inputArray[i] < ++cur)
       ;// find the repeated one
}

Method 2: (consider the given array element is from 1 to N)
1. Define an integer array occurNum[N] with intialize value 0s;
2. A for loop to find out how many times each number occurs in the given array
  for( int i=0; i<N; ++i )
 {
    occurNum[inputArray[i]-1] += 1;
 }
3. given a i, if occurNum[i]=0, then i+1 is the missing number. if it is 2, then i+1 is the repeated one.

drmfslx

• Aug 10th, 2007

 

Here is the working code for finding the duplicate number with no extra array.  The worst running time is 2N.  The aveage time would be smaller.

// return the repeated number
int findDup( int* data, int N, int* timeCounter )
{
    *timeCounter = 0;
    bool done=false;
    int i=0;
    while( i<N && !done ){
        ++(*timeCounter);
        while( i != data[i]-1 ){
            if( data[data[i]-1] == data[i] ){
                done = true;
                break;
            }else{ // swap the data[i] and data[data[i]-1]
                int temp = data[data[i]-1];
                data[data[i]-1] = data[i];
                data[i] = temp;
                ++(*timeCounter);
            }
        }
    }
    return data[i];
}

Notice that every swaping inside the while loop puts one element back to its right spot.  The total maximal number of swapping operations is N. Precisely it is N-1.  The for loop is O(N).  So the total performance is O(N).

sobin

• Sep 7th, 2007

 

1. Find RealSum = ( sum of all numbers in array )
2. Find RealProduct = ( product of all numbers in array )
3. Find ExpectedSum = n*(n+1) / 2     where n is number of integers
4. Find ExpectedProduct = n!

Equation 1 :  X - Y = (RealSum - ExpectedSum)
Equation 2 :  X/Y = (RealProduct / ExpectedProduct) 
             
Solve this equation.
X is the duplicated number
Y is the missing number

Stan Buyanov

 Profile Answers by Stan Buyanov 

• Jul 5th, 2008

 

//int a[] = {1,2,3,4,4,6,7,...N};
for (int i=0; i < N; ++i)
{
     if (a[i] ^ i+1)
     {
            std::cout << "missing number is " << i+1;
      }
 }

identitycrisis

 Profile Answers by identitycrisis 

• Sep 14th, 2009

 

#include<iostream>
using namespace std;
int main()
{
int a[]={1,2,3,4,5,5,6,8};
int sum=0,n=8,temp;
for(int i=0;i<n;i++)
{
    if(a[i]!=i+1)
    {
    temp=a[i];
    cout<<"Repeating element is "a[i]<<endl;;
    break;
    }
}
int tot_sum=n*(n+1)/2;

for(int i=0;i<n;i++)
sum+=a[i];

int miss=tot_sum+temp-sum;
cout<<"Missing element"<<miss;
return 0;
}