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 find out the duplicate number. Conditions: you have to do it in O(n) time without using any auxilary space (array, bitsets, maps etc..).

Which sort will you use with complexity O(n)? The sorting algorithms that I know have the complexities between O(nlogn) & O(n*n). Although radix sort claims to have complexity O(n) but that is for single digit numbers only. For larger N, I don't think you can sort in O(n) (worst case).

waiting for the reply...

use the following method:

mark the missing number as M and the duplicated as D

1) compute the sum of regular list of numbers from 1 to N call it RegularSum

2) compute the sum of your array (the one with M and D) call it MySum

now you know that MySum-M+D=RegularSum

this is one equation.

the second one uses multiplication:

3) compute the multiplication of numbers of regular list of numbers from 1 to N call it RegularMultiplication

4) compute the multiplication of numbers of your list  (the one with M and D) call it MyMultiplication

now you know that MyMultiplication=RegularMultiplication*D/M

at this point you have two equations with two parameters, solve and rule!

As the numbers range from 1 to N , you can create an array B of size N and then go through the original array A and put the number in the corresponding position in the second array. That is if the original array has A[1] as 4, then the mark the second array B[4] as true. Iterate through A. If a position in array B is already marked, then we have a duplicate.

Another solution would be to XOR each element A[1]XORA[2]XORA[3] and so on. When the answer becomes 0, the element in that position is the duplicate. This, i think can fail sometime.

1. hugeResult = temp = Arr[0] * Arr[1] * ... * Arr[N-1]

2. for i = N down to 1
           if (hugeResult is not divisible by i)
                   that is the missing number so break
            else
                 hugeResult = hugeResult/i
3.   hugeResult =  Temp // what was computed in part 1
      for i = N down to 1
            if (hugerResult is divisible by i*i)
                   than i was repeated so break and puzzle solved
             else
                  hugeResult = hugeResult / i


          

Another solution:
the question can convert to the following issue:
Assume a and b is const value,
X - Y = a
X * X - Y * Y = b
then what is the x, y value?

Another similar question:
There are n-2 numbers, which are from 1 to n, and no duplicate number, what are the missing 2 numbers?

Perhaps I am confused but I find none of the above answers correct according to the rules.  

1. vipin gupta stated why JC’s solution was incorrect.  Kudos to vipin gupta for being able to correctly read and interpret the problem he submitted and recognize a failed answer when he sees it.  vipin gupta, I hope you don’t mind if I explain the rest of these failed attempts on your wonderful conundrum.

2. David Rachutin’s answer is insufficient mainly for the reason that the problem clearly states that the solution may not have any auxiliary memory of the forms such as arrays, bitsets, maps, etc.  Why is this a problem?  In the second portion of his solution he suggests multiplying all the numbers in the array together.  Well, I’m thinking of an array that holds 50 million numbers (N = 50,000,000). 

 I’d like to know what programming language has an atomic numeric data type that would hold such a number as he describes in his variable RegularMultiplication (or even his variable MyMultiplication for that matter – which could very well be larger than RegularMultiplication, by the way) that is not an array and still contains the value of 8.262084864318990*10^5,565,708???? 

 (yes, that’s right, an 8 followed by 5 and a half million digits – more atoms than there are in the known universe – by many orders of magnitude – and by the way, I can think of even larger arrays, like one where N = 900 quadrillion).  Furthermore, just as an aside, the first portion of his solution, MySum can be reached by duplicating different numbers. 

Let’s use the first 5 digits of pi for example: 31415.  The 2 is missing and a 1 is duplicated but the summation is 14 – but then so is the summation of 12335, which is missing a 4 and has duplicated a 3.

 3.  jins answer is wrong because he/she can’t read.  Again, the problem clearly states that the solution may not have any auxiliary memory of the forms such as arrays, bitsets, maps, etc., but jins starts out his/her solution with the direct quote of “As the numbers range from 1 to N , you can create an array B of size N…”.  No, jins, you can’t, it says so right in the problem.  As for jins XORs solution, jins thinks it may fail sometimes and he/she is right – it fails if your first three numbers in ANY array of ANY size greater then two are 1, 2, and 3 (note that 001 XOR 010 XOR 011 = 000 and yet there have been no duplicates so far – and we still have 49,999,997 entries to go).

4. For the unnamed visitor who posted “solution” #5, where he/she calculates his/her variable hugeResult, I’ll defer him/her to my explanation of an array with 50 million entries and the resultant multiplication of all of those together explained above in my #2 rebuttal.

5. Concerning mywing’s solution – I have no idea because I guess I don’t have his/her font set on my computer and it all looks like gibberish.  So it may be a brilliant solution or the scrawling of a blindfolded, one-armed chimpanzee.  I would like to give him/her the benefit of the doubt and congratulate mywing on his/her solution.  Well done.

 
6. The actual solution that I came up with is quite elegant and I would provide it to you here in the margins if they allowed me a bit more space. J

Well its really simple all you need is one variable to iterate through the array.
I do not want to put the whole answer as somehting should be left for you guys to think too.
But the hint how about using the same array to denote we visited the number already???  ...

Much thanks to wywing for changing his font. I can now read his/her solution. However, I am still a bit confused by what mywing has written there: Another solution:
the question can convert to the following issue:
Assume a and b is const value,
X - Y = a
X * X - Y * Y = b
then what is the x, y value? First of all, how does the question magically convert to mywings 2 equations? Mywing states that variables a and b are constant values but without supplying a way to calculate them (perhaps part of the magical conversion process that he leaves as an obvious exercise for the reader) they become variables just like X and Y. Furthermore, without knowing *HOW* to calculate a and b we now have *TWO* equations and *FOUR* unknowns (X, Y, a, and b), which is, unfortunately, not solvable. Nevertheless, Id still like to give mywing the benefit of the doubt here with his solution if he/she would only be so kind as to provide a bit of information. Mywing, please provide a more detailed explanation of:


1) How to convert the original problem to your 2 equations.

2) How to calculate the constant value a.

3) How to calculate the constant value b.

4) Which number is missing (X or Y) and which is supposed to be duplicated (X or Y) or how does one back-convert X and Y to the missing and duplicated numbers.


Afterwards, of course, the solutions to mywings two equations are: x = (a^2 + b)/(2a), y = (b a^2)/(2a). Which leaves one to hope that b > a^2 (if both a and b are positive) or that a^2 > b (if both a and b are negative). Im still rooting for you, mywing. Please help us lesser intellectuals understand your wisdom here.

Hi purvid, Saw your answer and wanted to make a make a few suggestions/comments/questions.

Your answer was: Well its really simple all you need is one variable to iterate through the array.

I do not want to put the whole answer as something should be left for you guys to think too.

But the hint how about using the same array to denote we visited the number already?...

First of all, it doesnt seem that simple.

Second of all, the word something is spelled something instead of the way you spelled it (as something).

Thirdly, it is incorrect English to say something should be left for you guys to think too.

What you probably want to do here is change you last word of too to on.

Lastly, and most importantly, I would *VERY* much like to see this problem solved only using *ONE* variable to iterate through the existing array (I did it, but it did take me more than only *ONE* iteration variable). Lets all
remember that the list could be very long (say for example, N = 2^32-1) and could be required to be solved on a 32 bit architecture machine (so if youre thinking of negating each item in the list think again).

After seeing many of the failed attempts above I have resolved to solving this myself.  Here it is:


// Problem: There are numbers from 1 to N in an array. Out of these, one of the
//          numbers gets duplicated and one is missing. The task is to find
//          out the duplicate number. Conditions: you have to do it in O(n) time
//          without using any auxiliary space (array, bitsets, maps etc..).

// C Code Solution

// We always include these standard C header files although
// some of them may not be required for this program.
#include <stdio.h>
#include <stdlib.h>    
#include <ctype.h>
#include <sys/types.h>

// One can either define these here or in an include file.
// We have provided both as an example.
//
// #define INT  unsigned long int  /* any unsigned integer type will do here */
// #define N    ((INT)50000000)  /* N can range between 2 and the max of INT */
// INT A[N] =   { /* N random, whole numbers ranging from 1 to N */ };
//
// OR
//
// #include "ArrayProblemDefinitions.h"

#define bool          int
#define FALSE         0
#define TRUE          (!FALSE)
#define SWAP( X, Y )  {X ^= Y; Y ^= X; X ^= Y;}

// This program not only identifies the duplicated number and the
// missing number but may sometimes also fix and sort the array
// as well.
int main()
{
   INT   i         = 0;
   INT   missing   = 0;
   INT   duplicate = 0;
   bool  finished  = FALSE; 
  
   while ((!finished) && (i < N))
   {
      if (i + 1 == A[i])
      {
         i++;
      }
      else
      {
         if (A[i] == missing)
         {
            A[missing - 1] = missing;
            missing        = i + 1;
            A[i]           = missing;
            i++;
         }
         else if (A[i] != A[A[i]-1])
         {
            SWAP( A[i], A[A[i]-1] )
         }
         else if (A[i] < i + 1)
         {
            duplicate = A[i];
            missing   = i + 1;
            finished  = TRUE;
         }
         else
         {
            duplicate = A[i];
            missing   = i + 1;
            i++;
         }  // if
      }  // if
   }  // while

   printf( "The duplicated number is: %ld./n", duplicate );
   printf( "The missing number is: %ld./n", missing );
}  // main()

//a[n] array

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

now scan the array and return those numbers whose index does not match the element...

returned number is duplicate; index is missing number [:)]

Oh how I weep for the next generation of programmers.  Every answer to every question seems to be, “Oh, it’s so simple…”  Oh, to be young again and to think I know everything.

 

The latest to make a failed attempt at “it’s so simple” is Vandita with the following:

  //a[n] array

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

now scan the array and return those numbers whose index does not match the element...

returned number is duplicate; index is missing number [:)]  If I were grading this I would give it an F-, for not only does it *NOT* solve the problem in any way, but it also commits several “array-out-of-bounds” errors due to the fact that Vandita can not count. Vandita, here is the non-“array-out-of-bounds” version of your program, please try to notice the differences and then practice counting in your spare time: //a[n] array

for (int i =0; i<n; i++)
   swap( a[a[i]-1], a[i] );
 Secondly, it might be a *good* thing to actually test your “algorithm” on a set of numbers to see if it works before posting it to the entire world (how embarrassing).  Not only would this have helped you catch and repair your “array-out-of-bounds” errors but could have also *enlightened* you to the fact that your “simple” attempt does *NOTHING* to solve the problem. 

For example, try the first five digits of pi as a test run; 3, 1, 4, 1, 5.  This sequence of numbers is missing a 2 and duplicates a 1 (N = 5).  After running this sequence of numbers through the corrected version of your “simple algorithm” the sequence looks like this: 1, 4, 3, 1, 5.  Now performing a “scan” indicates 4 AND 1 as the *SINGLE* duplicated number, while 2 AND 4 appear as the *SINGLE* missing number.

here is my code

#include
using namespace std;
int main()
{
    int i,n;
    cout<<"Enter the length::";
    cin>>n;
    int A[n];
    for(int i=0;i<n;i++)
        A[i]=0;
    for(i=0;i<n;i++)
    {
        int j;
        cin>>j;
        A[j-1]+=n;
    }
    for(i=0;i<n;i++)
    {
        if(A[i]==0)
            cout<<i+1<<" is a missing numbern";
        else if(A[i]>n)
            cout<<i+1<<" is a duplicated numbern";
    }
}

here is my code.... simplest of all :)

private static void findDuplicate() {
    int[] array = new int[]{1,2,3,4,5,6,2,8,9,10};
    double sum = 0;
    double actualSum = 0;
    double product = 1;
    double actualProduct = 1;

    for(int i=0; i<array.length; i++)
    {
        sum += (i+1);
        actualSum += array[i];
        product *= (i+1);
        actualProduct *= array[i];
    }

    double y = (sum - actualSum)/(product/actualProduct - 1);   // duplicate no
    double x = (sum - actualSum) + y;   // original no

    System.out.println("x = " + x);
    System.out.println("y = " + y);

}

Jasvinder, nice idea! Too bad its not meant for this problem!

You see, a lot of the time the difficulties of a problem are hidden in how they
are carefully stated.

For example, *THIS* problem is stated, There are numbers from 1 to N in an
array. And *NOT* You can allow the user to enter numbers from 1 to N in an
array of your choosing.

The array *ALREADY EXISTS* with numbers in it.

One could use your approach by creating a duplicate array and reading in the
numbers from the original array just as if they came from the user

but then the author of the problem *ALSO* states that you have to do it without
using any other auxiliary space (such as a duplicate array).

It seems that the author went to a bit of trouble trying to prevent such an easy
solution as yours unfortunately no one seems to be able to read out there.

But hey, other than not being able to read the problem correctly you did a fine
job at solving some other problem.

Well done! It was, indeed, a very creative solution to some other problem that
none of us are concerned with here.

And best of luck to you if you do ever try to solve *THIS* problem.

Abhijeet, have you not read the attempted solutions above or my explanations
as to why they (AND yours) do not work?

Everyone else, please listen up
so I dont have to do this another time.

Pick an architecture ANY architecture, 32 bit, 64 bit, 128 bit, etc.

No matter which architecture you pick your variables; sum, actualSum, and
actualProduct *ARE ALL GOING TO OVERFLOW*.

You may think that because you declared them as doubles that they wont overflow
your *SUPER* enormous variables.

Well, lets try a test. Lets suppose that your simplest of all program was
written on a machine with a 32 bit architecture.

That means that your int array could be as large as 2,147,483,647 entries.

Now do you really think that you can contain (without ANY loss of precision) the
product of 2,147,483,647 numbers (called 2,147,483,647 factorial or
2,147,483,647! for short) in your variable

actualProduct, which is only allotted 8 bytes on a architecture of 32 bits?

Your program will fail for an array sized as low as 50 entries!!!

Sure your double will record the product of all of the numbers in the array as
3.04140932017134 x 10^64

but thats only because your eight byte double variable only keeps 15 digits of
accuracy, when in fact, the real answer is
30,414,093,201,713,378,043,612,608,166,064,768,844,377,641,568,960,512,000,000,000,000
with out losing *ANY* precision.

Now if your program fails with an array as low as 50 entries and it can be as
big as 2,147,483,647 entries (and thats a signed int an unsigned 32 bit int
would be 4,294,967,295 entries) your program is going to overflow all over the
place - *EVEN ON THE SUMS* that you keep in sum and actualSum

and the author never says *ANYTHING* about limiting the size of the array to a
*SIGNED* int.

In fact, I dont believe that you can guarantee that your simplest of all
program will work on any arrays longer than 17 entries (such as the following:
int[] array = new int[]{2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17,
17}).

You were definitely right when you coined your program as being the simplest of
all it *REALLY* is simple since it only handles arrays ranging in size from 1
to possibly 17.

If thats not bad enough, some compilers (such as GNU) allow to you declare:
unsigned long long [] = new unsigned long long{23, 51, 98, 405, 16, };

This means that your unsigned long long integer uses the same amount of space
(bytes) as your doubles (again, 8 bytes on a 32 bit architecture).

Which means that theres no reason why your array cant have
18,446,744,073,709,551,615 entries (except that it probably wouldnt fit into
memory).

Now, again, remember that this is all best case scenario here since I gave you
the benefit of the doubt and used a 32 bit architecture try using a 64 bit or
128 bit architecture and see what happens.

Jasvinder, sorry about the cursory review I gave your program earlier today.


Now that Ive had time to fully examine it Ive found a plethora of blunders on
your part.

After it asked me to, Enter the length::" I typed in: -20 which seemed to
frustrate your program.

However, that mistake of entering a signed int and then using that possibly
negative number to allocate space to an array can be fixed.

I tried again, this time I entered: 1,000 factorial

You program didnt seem to handle that well either.

Next I tried 4,000,000,000 thinking that you may be on a 32 bit architecture
system.

Everything seemed fine until I entered the 2,147,483,648th entry and then it got
all fussy and temperamental

it was almost as if some thoughtless person had declared an array of *SIGNED*
ints when the problem clearly states that the array is filled with values from 1
to N

Finally, in desperation, I entered 1,500,000,000 but even then your program
failed to find the duplicated number.

Why? Because the author of your program (namely you) probably doesnt understand
what integers are in 32 bit, 64 bit, or even 128 bit architectures.

1. First sort the array
2. a[i] + a[N-2] = N

Whichever does not satisfy the condition either a[i] or a[N-2-I] is the repeated one.

eg if N = 100

1 + 99 = 100
1 + 98 = 100

Thanks

TofuAvenger

Thanx for your suggestion . Here is my updated code based on the same idea meant for *THIS* problem


#include
using namespace std;
void Find(int A[],int n)
{
int i;
for(i=1;i<=n;i++)
{
if(A[i]>0&&A[i]<=n)
{
A[A[i]]+=n;
}
else if(A[i]>2*n)
{
A[A[i]-2*n]+=n;
}
else
A[A[i]-n]+=n;
}
for(i=1;i<=n;i++)
{
if(A[i]<=n)
cout< else if(A[i]>2*n)
cout< }
}
int main()
{
int i,n;
cout<<"Enter the length::";
cin>>n;
int *A=new int[n+1];
for(i=1;i<=n;i++)
cin>>A[i];
Find(A,n);
}

TofuAvenger
One thing i want to remind you that the size of the array can not exceed the virtual memory size which is mostly the double of RAM.

So the length of the array has nothing to do with the CPU Architecture if we are concerned with the maximum size of the array.

One Thong More ,You are entering -20 in the length of array which is absolutely stupid .
we are here for the algorithms not for these type of testings.

Connect, learn how to read and then how to sort.  The problem clearly states: "Conditions: you have to do it in O(n) time".  Please tell all of us if you have the *MAGIC* sorting algorithm that sorts in O(n) time.  The entire community of both computer scientists and mathematicians will be *VERY* eager to see your O(n) sorting routine.  In fact, they’ll be so happy that you can pretty much stop answering questions on this forum and post your routine world wide and win a Nobel prize.  So, quit wasting time here and post this routine – unless it is the case that you are completely oblivious to sorting routines and the times required to perform them (which is the more probable of the two cases here). 

Wrong and wrong (yet again).

 

Did I miss something in the problem that stated that the array had to fit in your RAM?  This array could and likely *IS* stored on my external 500 GByte hard drive (or something with even more storage than my personal external hard drive).  Just because you can only read things in 2 x RAM size at a time doesn’t limit the author in any way, shape, or form concerning his problem.  You may *WISH* that it nicely fit into your RAM but then that’s why there are these interview problems out there – to separate the wheat from the chaff.

 

Oh, and by the way, “me entering -20 in the length of array is *NOT* absolutely stupid”.  This is a problem on a site for interview questions that are asked by interviewers to interviewees to determine whether or not the interviewer thinks they should hire the interviewee.  They will look for things like this.  How do I know?  Because I am interviewer and I do look for these things.  Also, I have been in interviews where they asked questions such as these and *DID* observe whether I was too lazy or inexperienced to put an “unsigned” in front of my “int” declaration for a value that could only be 1 to N.  They are not just interviewing you, one person.  They are interviewing a plethora of candidates, half of whom may have gotten the answer right.  So when it comes to the final decision, you can literally bet your job that they will look for things in order to weed out the candidates; “This person got the correct answer but didn’t account for overflow”, “This person got the correct answer but allowed the user to enter a negative number in the allocation of his array”, etc.  Besides, even if you don’t agree with me isn’t it better to be safe than sorry?  Why in the world would a seasoned software engineer code any other way than safely – even for just a test program or just an algorithm program??

Jasvinder, I thought after my comments you’d have changed this answer yet again over the last few days (would it kill you to type the word “unsigned” ??) but I suppose you guess that it is good enough to stand.  Well, guess again.  It *STILL* is not the answer for *THIS* problem and you don’t seem to get why (if you are actually mentally challenged I do, sincerely apologize at this point and bid you to read no further – your answer is fine, please go back to eating PLAY-DOH). 

 

You believe that if you change the problem to have the user enter all of the entries, you can ignore overflow.  That is probably true.  If you have the user enter the length of the array (and check that it does not overflow your virtual memory – which you fail to do, by the way) it will fit nicely into virtual memory and that will not overflow most modern day architectures.  However, the problem says (quoted directly), “There are numbers from 1 to N in an array.”  Perhaps you missed that part – that the numbers are already in an array that already has a specified ‘N’ – meaning, specifically, that THE USER DOES NOT GET TO SPECIFY ‘N’ OR THE NUMBERS IN THE ARRAY.  I don’t understand how the author or I can state that more clearly – yet you still seem to think that your solution (the solution you have provided to some other problem WHERE THE USER DOES GET TO SPECIFY ‘N’ AND THE NUMBERS IN THE ARRAY) is the same as this one (thanks for solving that other problem – I think you nailed it – great job, but we should probably think about starting to solve the author’s problem now).

 

There is of course, another possibility; English may not be your primary language.  If this is the case, you should let the author know so that he/she can translate the statement of the problem for you in your native tongue.  Perhaps then you will understand why THE USER DOES NOT GET TO SPECIFY ‘N’ OR THE NUMBERS IN THE ARRAY.

 

Otherwise, keep in mind that, for *THIS* problem, ‘N’ is specified *BEFORE* the execution of any potential solution code, may *NOT* fit into your virtual memory, and may definitely *OVERFLOW* a simple int in a 32 bit architecture.

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 ++(*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);
}
}
++i;
}
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).

I am wondering if it works. Lets consider 3 is the missing number and multiple of 3 that is 6,9 etc may be the duplicated number. In that case you can't get a break point in the first loop as any number divisible by 6 is divisible by 3.similary just byknowing that the total product is a multiple of 36(6*6) we can't say that 6 is duplicated because even 4*9 is 36.

Let me know if thw way i understood it is wrong.

Thank you.

import java.util.Arrays;
import java.util.Random;


public class OneToN {

public static void main(String[] args) {
int len = 100 ;

int[] num = new int[len] ;
fillArray(num,len);
long x = 0,y = 0 ,z = 0 , Missing , Duplicate ;
for(int i = 0; i < num.length ; i++)
{
System.out.print("n " + num[i]);
x += ( (i+1) - num[i] ) ;
y += ( (i+1) * (i+1) - num[i] * num[i]);
}
z = y /x ;
Missing = (z+x)/2 ;
Duplicate = (z-x)/2;
System.out.print("nFound Missing ::: " + Missing);
System.out.print("tDuplicate ::: " + Duplicate);
}
static void fillArray(int[] n, int len)
{
for(int i = 0 ; i < len ; i++ )
n[i] = (i + 1) ;
Random r = new Random();
int Missing = r.nextInt(len /2 ) ;
int Duplicate = r.nextInt(len/2) ;
n[Missing - 1 ] = Duplicate ;
System.out.print("nSelected Missing = " + Missing + "ttDuplicate = " + Duplicate);
}
}

This seemed like a nice solution but it will fail on this input:

1 2 3 4 5 5

clearly number 6 is missing, but your product is divisible by 6 and your algorithm won't find it.

radix sort is not only for single digit integers :P what is the point of sorting single digit integers and i would also like to know the o(n) algorithm suggested by him

int FindDupNMissing(unsigned int N, unsigned int Arr[], unsigned int &Dup, unsigned int &Missing)
{
   if (N < 1)
       return -1;
   
    // if N is bigger below formula, then we this alg will not work. As it adds all numbers in an unsigned int.
   if( N > (2 * (static_cast(pow(UINT_MAX, 0.5)) - 1)
       return -1;

   unsigned int ActualSum = 0;
   unsigned int ExpectedSum = (static_cast(pow(N, 2.0)) + N) / 2;

   for(unsigned int i = 0; i < N; i++)
   {
        if(A[A[i]-1] == A[i])
             Dup = A[i];
        else
        {
             swap(A[A[i]-1], A[i]);
             Sum += A[i];
         }
   }

   Missing = ExpectedSum - ActualSum;

   return 0;
}

Actually there is one correction needed for above:

    // if N is bigger below formula, then we this alg will not work. As it adds all numbers in an unsigned int.
   if( N > (static_cast(1.4142 * pow(UINT_MAX, 0.5) - 1)) )
       return -1;

Actual formula is MaxSupportedNumber = pow( (2*UINT_MAX + 0.25), 0.5 ) - 0.5

It will overflow, so I have move moved pow(2, 0.5) outside and simplified it.

Of course, if we can use larger data type we can increase our supported limit.

int FindDupNMissing(unsigned int N, unsigned int A[], unsigned int &Dup, unsigned int &Missing)

{

    if (N < 1)

      return -1;

 

     unsigned int ActualSum = 0;     unsigned int ExpectedSum = (static_cast<unsigned int>(pow(N, 2.0)) + N) / 2;
     for(unsigned int i = N-1; i != UINT_MAX; i--)

     {

      if(A[i] - 1 != i)

         swap(A[A[i]-1], A[i]);

      }

      for(unsigned int i = 0; i < N; i++)

      {

          if((A[i] - 1 != i) && A[A[i]-1] == A[i])

              Dup = A[i];

          else

          {

               if(A[i] - 1 != i)

                     swap(A[A[i]-1], A[i]);

                

               ActualSum += A[i];

               if(ActualSum < A[i])

                      return -1; //we have overflowed

           }

      }

      Missing = ExpectedSum - ActualSum;

      return 0;

}

"Please tell all of us if you have the *MAGIC* sorting algorithm that sorts in O(n) time.  The entire community of both computer scientists and mathematicians will be *VERY* eager to see your O(n) sorting routine.  In fact, they’ll be so happy that you can pretty much stop answering questions on this forum and post your routine world wide and win a Nobel prize.  So, quit wasting time here and post this routine – unless it is the case that you are completely oblivious to sorting routines and the times required to perform them (which is the more probable of the two cases here). "


I don't know why you have to jump down people's throats when they make a mistake...

Anyways, it's no *MAGIC* in this case...  Normally, sorting in O(n) time would be a pipe dream, but this is no ordinary array.  We have more information than that.  In fact, we know if contains all the numbers from 1 to N except one, and that one is duplicated in its place.  This is MORE than enough information to sort the array in O(n) time with the duplicate ending up in the missing number's position.

for (int i = 0; i < N; i++) {
    Swap (A[A[i] - 1], A[i]);
}

That should get the job done..  Tell me how that's not O(n)?

Remember we have a lot of information about this array.  Don't assume O(n) sorting is impossible.

Once it's sorted it should be easy to run through and look for the answer
done = false;
i = 0;
while (i < N && !done) {
    if (A[i] != i+1) {
       Duplicate = A[i];
       Missing = i + 1;
        done = true;  
    }
    i++;
}

excuse the psuedo code...

O(2N) is the worst case.  Should be less.

for (int i = 0; i < N; i++) {
    Swap (A[A[i] - 1], A[i]);
}

That should get the job done..  Tell me how that's not O(n)?



LOL!  Gosh, you're really smart!  You are correct about one thing however, the NON-sorter that you've written IS O(n)!  Now if you could just get it to actually sort.  You want to know the reason why I "jump" down people's throats?  Look in a mirror.  Then get a job at a Mc Donald's, you're clearly not suited for this type of work.  People like you who "think" they can code, working at MicroSoft - that's the reason we have the *super* stable Vista as an OS.

for (int i = 0; i < N; i++) {
    Swap (A[A[i] - 1], A[i]);
}

That should get the job done..  Tell me how that's not O(n)?



LOL!  Gosh, you're really smart!  You are correct about one thing however, the NON-sorter that you've written IS O(n)!  Now if you could just get it to actually sort.  You want to know the reason why I "jump" down people's throats?  Look in a mirror.  Then get a job at a Mc Donald's, you're clearly not suited for this type of work.  People like you who "think" they can code, working at MicroSoft - that's the reason we have the *super* stable Vista as an OS.




First of all, you're right.  I was wrong in the way I stated to find the duplicate.  And yes it doesn't entirely sort the array, but it doesn't need to.

Also, could you be any ruder?  I don't know if it makes you feel better about yourself to do this or what, but in any case here's my updated algorithm.

nice and short.

for (int i = 0; i < N; i++) {
    if (A[A[i]-1] == A[i]) {
       duplicate = A[i];
       break;
    }
    Swap (A[A[i] - 1], A[i]);
}


Since the task is only to find the duplicate, not the missing number, this gets it done in O(n) time.  The list isn't entirely sorted, but it does put the duplicate's first incarnation in a place that the second one can find it.  It will sort i/N of the list.  And no it wouldn't completely sort the list in one pass, but that's not the question.

This solution is O(n) in the worst case.  Which is that the last number A[N-1] is the duplicate.

Check the solution......complexity o(n)


#include <string.h>
#include <unistd.h>
#include <stdio.h>
#include<stdlib.h>
main()
{
int *a,i,n;
float actualproduct=1,dup = 0,mis = 0,originalsum=0,actualsum=0,originalproduct=1,diff=0,quo=0;
printf("Enter Nn");
scanf("%d",&n);
a = (int *) malloc( n * (sizeof(i)));
printf("enter the %d numbersn",n);
for(i=0;i<n;i++) {scanf("%d",&a[i]);}
for(i=1;i<=n;i++)
 {
  originalproduct = originalproduct * i;
  originalsum = originalsum+i;
 }

 //printf("org product = %.0fn",originalproduct);
 //printf("org sum = %.0fn",originalsum);
for(i=0;i<n;i++)
 {
  actualproduct = actualproduct * a[i];
  actualsum = actualsum+a[i];
  }
//printf("act sum = %.0fn",actualsum);
//printf("actproduct = %.0fn",actualproduct);  
diff = originalsum-actualsum;
//printf("diff = %.0fn",diff);
quo = originalproduct/actualproduct;
//printf("quo = %.0fn",quo);
 dup = diff/(quo - 1);
 mis = diff+dup;
 printf("Missing number = %.0fn",mis);
 printf("Duplicate number = %.0fn",dup);
 free(a);
 }   




 

Here is the solution without having to worry about overflow problems:

/* Problem: There are numbers from 1 to N in an array. Out of these, one of the
            numbers gets duplicated and one is missing. The task is to find
            out the duplicate number. Conditions: you have to do it in O(n) time
            without using any auxiliary space (array, bitsets, maps etc..). */

/* C Code Solution */

/* We always include these standard C header files although */
/* some of them may not be required for this program.       */
#include <stdio.h>
#include <stdlib.h>    
#include <ctype.h>
#include <sys/types.h>

#define INT  unsigned long int  /* any unsigned integer type will do here   */
#define N    ((INT)7)           /* N can range between 2 and the max of INT */
INT A[N] =   { 1, 2, 5, 5, 3, 4, 6 };
  
#define bool          int
#define FALSE         0
#define TRUE          (!FALSE)
#define SWAP( X, Y )  {X ^= Y; Y ^= X; X ^= Y;}

/* This program not only identifies the duplicated number and the
   missing number but may sometimes also fix and sort the array
   as well. */
int main()
{
   INT   i         = 0;
   INT   j         = 0;
   INT   missing   = 0;
   INT   duplicate = 0;
   bool  finished  = FALSE; 
     
   while ((!finished) && (i < N))
   {     
      if (i + 1 == A[i])
      {
         i++;
      }
      else
      {
         if (A[i] == missing)
         {          
            A[missing - 1] = missing;
            missing        = i + 1;
            A[i]           = missing;
            i++;
         }
         else if (A[i] != A[A[i]-1])
         {
            j = A[i] -1;
            SWAP( A[i], A[j] )
         }
         else if (A[i] < i + 1)
         {
            duplicate = A[i];
            missing   = i + 1;
            finished  = TRUE;
         }
         else
         {
            duplicate = A[i];
            missing   = i + 1;
            i++;
         }  // if
        
      }  // if
   }  // while

   printf( "The duplicated number is: %ld.n", duplicate );
   printf( "The missing number is: %ld.n", missing );
  
   return( 0 );
}  // main()

what's the time complexity of your algorithm?

TO TofuAvenge  post #37:

         else if (A[i] != A[A[i]-1])
         {
            j = A[i] -1;
            SWAP( A[i], A[j] )    <---- how many SWAPs are you expecting in total?
         }

Let the missing number be m and the duplicate be d.

Calculate the sum of the numbers present, call this calc_sum

 According to summation formula, summation (1+ 2 + ....N) = (n*(n+1))/2 - call it sum_real

sum_real = calc_sum + m -d  (taking out the duplicate & adding the missing )
m - d = sum_real - calc_sum


Calculate the sum of squares , call it calc_sum_sq

According to summation formula, summation (1*1 + 2*2 + ...+N*N) = (n*(n+1)(2n+1))/6 - call it sum_sq_real

m*m  - d*d = sum_sq_real - calc_sum_sq

(m+d)(m-d) = sum_sq_real - calc_sum_sq

We know the value of m-d

So we have two linear equations with two unknowns:

m + d = (sum_sq_real - calc_sum_sq ) /(sum_real - calc_sum)

m - d  = (sum_real - calc_sum)

Solve the two. Since we only computed the sum and sum of squares, the algorithm runs in O(n)
and not addition array etc was used.

I think someone already posted a similar solution but wasnt very clear. 

HTH

# Perl - The algorithm finds the duplicate value by using the given
# array to track the values that have been encountered as the
# array is iterated from the beginning to the end. Each element of
# the array tracks the value that would be contained at the
# element's position if the array was sorted. For instance, array[0]
# tracks the value 1, array[1] tracks value 2, and array[N-1] tracks
# the value N. When an array element is iterated, the element's
# value is used to index into the array (array[array[currentIndex] - 1]).
# If the value is zero, then the number has already been encountered
# and the duplicate has been found, otherwise, keep looking.

# Get an array of integers from 1 to 1000000 with one
# duplicate value and one missing value and in random order.
my @numbers = &GetNumbers(1000000);

# Start from the beginning.
my $curIndex = 0;

# While the array value identified by the current index's value used as
# an index into the array, is not zero then the current index's value
# hasn't been encountered, yet.
while ($numbers[$numbers[$curIndex] - 1] != 0)
{
  # Copy the value at the array offset identified by the current index's
  # value to the offset identified by the current index. Zero out the
  # element at the array offset identified by the current index's
  # value.
  ($numbers[$curIndex], $numbers[$numbers[$curIndex] - 1])
    = ($numbers[$numbers[$curIndex] - 1], 0);

  # Increment the current index if the value swapped to the array
  # position identified by the current index is equal to the value
  # that is tracked by the current index position. If incrementing
  # the current index places the index onto an array position that
  # is tracking an encountered value, increment the current index,
  # again.

  while ((($curIndex + 1) == $numbers[$curIndex])
    || ($numbers[$curIndex] == 0))
  {
    # Zero the value at the current index positon before incrementing
    # the current index. This is necessary for the case where the
    # current value is encountered in the array position that tracks
    # the current value.
    $numbers[$curIndex++] = 0;
  }
}

print "The duplicate number is $numbers[$curIndex].n";

We can use the same array for this. Use the value as index and update the value at index as visited.

Start with first number, use this as an index and update value at that location as -1. again pick the actual number in the updated location and repeat the above sequence.
If we get to location where the value is -1 or the same value we have the dubplicate number.

currloc = 1;
temp = 0;
while(1)
{
    if(A[currloc] == -1 || A[currloc] == currloc)
        --duplicate no is currloc
        break;
    currloc = A[currloc];
    temp =  A[currloc]
    A[currloc] = -1;
    currloc = temp;
}

Logic is
1. Missing Num - Actual Num = Expected sum - Real sum
2. Missing Num/Actual Num = Factorial_N/Found Prod

Expected sum = N(N+1)/2;
Real Sum = A[1]+....+A[N]; /// O(N)

Factorial_N = N! /// O(N)
Found prod = A[1].A[2]....A[N-1].A[N]; //// O(N)

Missing Num - (Found prod/Factorial_N)*Missing Num = Expected Sum - Real Sum;

its quite simple.. traverse the array..since there are 1-N elements..place the ith element that is a[i] in location a[a[i]]..that is if a[i]=j. swap this with element in location a[j].. if the existing element in a[j] before you perform the swap is already "j" then this is your required number..i hope u got it..

Here is the program written in C, which gives a solution for finding duplicate with O(n) time complexity and with using auxilary space:
#include<stdio.h>
#include<conio.h>
#define N 5
void main()
{
 int a[N+1] = {0,1,3,4,5,1}; //consider a[1] - a[N] as the given array
 int i;
 
 for(i=1;i<=N;i++)
 {
  if(a[i]<=N)
  {
   if(a[a[i]]>N) printf("%d is duplicated", a[i]);
   else a[a[i]] +=N;
  }
  else
  {
   if(a[a[i]-N]>N) printf("%d is duplicated", a[i]-N);
   else a[a[i]-N] +=N;
  }
 }
 getch(0);

}

Sorry for the typo in the solution given by me earlier. The solution does not use auxiliary memory.

The xor method that Jins proposed won't work. If we have the first 3 elements of the array as 1, 2 and 3. Then the xor of these 3 would be zero but there's no repeatation here.

my solution:
  

public void findDuplicate(){
        int[] a = {1,3,4....N};
        int origValue;
        boolean done = false;

        for (int i=0; i<a.length&&!done; i++){
            origValue = a[i];
            if (a[i]<0)
                origValue = -1*a[i];

            if (a[origValue-1] < 0){
                    done = true;
                    System.out.println("Duplicate number: " + origValue);
            }
            else {
                    a[origValue-1] = -1*a[origValue-1];                      
            }
            
        }

Let the missing number is M and the duplicate number is D.

1. Compute X = 1 XOR 2 XOR ... XOR N xor A[1] xor A[2] xor ... xor A[N]
X will be equal to M XOR D. Now find any non-zero bit B of X. It exists because X is not zero.

2. Compute two values
Y = XOR of numbers from 1 to N and elements of array A which have bit B equal 1
Z = XOR of numbers from 1 to N and elements of array A which have bit B equal 0
One of these two numbers will be M and the other will be D.

3. Find which one Y or Z exists in A and therefore is equal to D using one more pass through the array.

We are having an array of size n and is made of numbers 1 to nhaving one number missing and one duplicated.
We will find sum of this array and subtract from it the standard sum of integers i.e. n*(n+1)/2.
Now we get the value of duplicate-missing.

similarly we find the values of duplicate^2 - missing^2.

Using these two equations we can easily find values of missing and duplicate number,
Also we traversed array only one time to find sum of elements and sum of square of elements.
We consumed only two memory locations for storing both sums.
Hence space complexity is o(1) and time complexity is o(n).

The numbers are 1 to N, with say the number x replaced by y.

Original Array: 1 2 3 4 5 6 ... x .... y ... N == N * (N+1)/2
New Araay:      1 2 3 4 5 6 ... y ... y ....N

Sum of Origianl array = 1 + 2 + 3 + .... N == N * (N+1) * (2N+1) / 6
Sum of New array = Original Sum + ( y - x)

Sum of squares of Original Array = 1 + 4 + 9 + .... N*N
Sum of squares of New Array = Original square Sum + ( y * y - x * x)

y - x == sum of new array - N * ( N + 1) / 2
y^2 - x^2 == sum of new array squared - N * (N+1) * (2N+1) / 6

now we know that y^2 - x^2 == (y-x)(y+x)

Find y+x and then add it to y - x and divide by 2 :-)

You need to iterate through the array twice.

In the first iteration

1. Read the value (say i) from the current index
2. Check the value at the index using the first value (i.e. check Array [i-1] assuming array index starts from 0 in the language you are using)
3. If that value is the same (i.e. i in this case) then we have found the duplicate. Store 0 in the current index
4. Else if the value (i) is not 0, exchange the values (you can do the exchange without using extra storage by doing 3 XOR operations)
5. Complete this iteration till N-1. Do not need to check the Nth value. It is guaranteed to be N or 0 by the time we reach there

In the second iteration, just traverse the array till we find 0. That is the missing number.

asumptions
a[1..n] = { 1 to n with one missing n one duplicate element };
means 1<=a[i]<=n for all 1<=i<=n;

we will put a[i]=-1 once ith element visited.

here we go:

i=a[1];

while(i<=n)
{
if(a[i] == -1) return i;// ith element is already visted hence i is the duplicate number.

else if (a[i] == i)
{
a[i]= -1; //ith is  visited now

//find next i,

while (i<=n && a[i]==-1) i++;

//check if i >n
if(i>n) i =1;
while (i<=n && a[i]==-1) i++;
i=a[i];

}
else
{
temp=a[i];

a[i]= -1; //visited now;
i=temp;
}

}//end of while

public int[]
GetMissingAndDuplicateValue(int[] ValueArray)
{int As = 0;
int Ap = 0;i
nt Bs = 0;
int Bp = 0;
for ( int i = 0 ; i < ValueArray.Length ;
i++ ) {As += i;Ap += ( i * i ) + ( 2 * i );
Bs += ValueArray[i];Bp += ValueArray[i] * ValueArray[i];}As += ValueArray.Length;Ap += ValueArray.Length;int DuplicateValue = Ap - Bp - ( As * As ) + ( 2 * As * Bs ) - ( Bs * Bs );DuplicateValue /= ( ( 2 * As ) - ( 2 * Bs ) );
int MissingValue = As - Bs + D;return new int[2]
{ DuplicateValue, MissingValue };}

Very simple: Missing number / Duplicate number :: N! / multiplication of all numbers in given array

For example lets say value of N = 5 and the input array is 1,2,3,4,4. Here missing no. is 5 and duplicate no is 4.

By making use of the above equationMissing number/Duplicate number :: 1*2*3*4*5 / 1*2*3*4*4 (1,2,3,4 will cancel each other in numerator and denominator)

After solving this u get Missing no = 5 and Duplicate number = 4

Now to solve this programmatically u need to reduce the factor ( N! / multiplication of all numbers in given array) such that the value in numerator and denominator is less than or equal to N.In the above case u will have to reduce 120/96 to 5/4.

And this can be done in O(1).So the total time complexity of this solution is O(n)!!!

Here is the code for this

Code
#include<stdio.h>
#include<stdlib.h>
 
main()
{
 
 int i, n ,j ,k ;
 int *input ;
 printf("enter the size of the array 
");
 scanf("%d",&n);
 input = (int *) malloc(sizeof(int)*(n+1));
 for(i = 1; i<= n ; i++) // values stored in 1 to n for convinience !!!!
 {
        printf("Enter the value .... should be between 1 and %d
 " , n );
        scanf("%d",&input[i]);
 }
 
 for( i =1 ; i<=n ;i++ )
 {
   if( input[input[i]] < 0 )
        printf( "%d value has been repeated...",input[i]);
   else 
  {
        input[input[i]]= -input[input[i]];
  }
 }
 
for( i = 1 ; i<= n ; i++)
 if(input[i]>0)
        printf("%d value has been missing ", i);
}

I don't think that's a right way. How r u going to get D and M question doesn't specify that u will get the duplicate number

Assume element m is repeated in place of p.

Code
sum = 0;
square = 0
for each element in array
    sum+=element
    square+=(element)^2
end
 
p-m = n(n+1)/2 - sum   ...............(1)
p^2-m^2 = n(n+1)(2n+1)/6 -square
=> (p+m)(p-m) = n(n+1)(2n+1)/6 - square ..............(2)
Divide (2) by (1), we get the value of 
p + m = [n(n+1)(2n+1)/6-square)]/[n(n+1)/2 - sum]........(3)
 

solve (1) and (3) for values of p and m.

The important things here are:

1. O(n) means that we will have to sort the array and examine it for the duplicate number at the same time. We cannot sort it and then look at the sorted array as that would be O(2n)

2. We only have to find the dup number, not the missing number.

int i=0;

while (i {
if (A[i] == i+1)
{
// In the right place already - advance
++i;
}
else if (A[A[i]-1]) == A[i])
{
// Duplicate
return A[i];
}
else
{
Swap (A[i], A[A[i]-1]);

if (A[i] == i+1)
{
// In the right place already - advance
// Need to check this here as if we let it get checked in the next iteration of the loop we will not have O(n)
++i;
}
}
}

return 0; // No dup found

Numbers are from 1..N. What stands out is that 0 is not in the list We are not asked to find the missing number. The following simple solution will work. The algorithm is to take the first number x, set arr[x] = 0 and move the value that was to i; If the value that was at i was 0 then x is the duplicate number.

Code
int iCurrent = 0;
 
for (int (i=0 ; i<N ;)
{
    int currNum = arr[i];
    if (currNum == 0)
    {
        // i has already been found and thus set to 0
        ++i;
        continue;
    }
 
    if (arr[CurrNum-1] == 0)
    {
        return currNum;
    }
 
    arr[i] = arr[currNum-1];
    arr[CurrNum-1] = 0;
}
 

Get two equations :
one using sum of numbers and other using sum of squares of numbers
two variable two equation ... solve them and the numbers

This solution

#define N ((INT)8) /* N can range between 2 and the max of INT */
INT A[N] = { 1,2,3,4,5,7,3,8 /* N random, whole numbers ranging from 1 to N */ };

it outputs:

hu@aurora:~$ ./a.out
The duplicated number is: 3./nThe missing number is: 7./nhu@aurora:~$
Let aside the /n that should be
and the %ld which should be %lu (unsigned long!), where in the problem was it stated that the array of integers is SORTED, which your code implies? At least it finds the duplicate...

Hello, this is my answer, and these are its features: 1) It runs in O(n), I know that it does not look like O(n) because of the while inside the for, but believe me if you really look deep you will see that it is actually O(n). 2) it does not change the value to the elements in the array (making negatives or adding N) this changes would most likely interfere with the value type and we would't want that right TofuAvenger. 3) It does not use an aux variable to swap the values, again thanks TofuAvenger. 4) It does not need to sort the entire array if not needed, only until the duplicate and missing elements are found, so if the duplicated value is in the lows, it is actually much faster than O(n). 5) The language is c# but it uses mainly anything you would use on C++ or C.

Code
        /// <summary>
        /// Finds the first/lowest duplicate and missing element in O(n) time
        /// Worst case scenario works in O(2n) but since constants are excluded from the O notation, it can be considered as O(n)
        /// </summary>
        /// <param name="A">Array of values 1 to N where N is the size of array</param>
        void FindDuplicate(int[] A)
        {
            int N = A.Length;
            
            int duplicate = 0;
            int missing = 0;
 
            //Sort the array, appears as larger than O(n) but in practice is indeed O(n) and most of the time less than O(n)
            for (int i = 0; i < N; i++)
            {
                //while the number on the position is not correct and the numbers to swap are different then swap
                while (A[i] != i + 1 && A[A[i] - 1] != A[i])
                    Swap(ref A[A[i] - 1], ref A[i]);
 
                //if the position i remains with a non-corresponding number and the numbers to swap 
                //are the same then we have found our duplicate and missing elements
                if (A[i] != i + 1 && A[A[i] - 1] == A[i])
                {
                    duplicate = A[i];
                    missing = i + 1;
                    break;
                }
            }
 
            //Display the result
            if (missing == 0)
                Console.WriteLine("No Duplicate found");
            else
            {
                Console.WriteLine("Duplicate: " + duplicate);
                Console.WriteLine("Missing: " + missing);
            }
        }
 
        /// <summary>
        /// Swaps 2 values by reference without using an aux variable
        /// </summary>
        /// <param name="a"></param>
        /// <param name="b"></param>
        private void Swap(ref int a, ref int b)
        {
            a ^= b; b ^= a; a ^= b;
        }
 

Code
I = 1
Do while I > N - 1
If num-array(I) - num-array(i+1) = 0
  Printf "duplicate number is " num-array(I)
  I = N + 1
else
  I = I + 1
End-If
End-Do
 

The solution assumes there are integers from 0..n for simplicity. The code below traverses the array and swaps the current element to its right location. While doing so it checks if the same number is already present at destination location. If yes then the number is duplicate. The code below takes O(n) to find solution. find Duplicate
(int[] arr)
{
int n = arr.length;
for(int k = 0; i < arr.length; i++)
{
if (arr[i] != i)
{ //There is already same number at this place
if (arr[arr[i]] == i)
return i;
swap(arr[arr[i]], arr[i]);
}
}
}

Let sum of 1 to n be totalSum
Let sum of the numbers in array be arraySum
var diff=totalSum - arraySum
Repeated number=n - (diff)
Missing number= n+(diff)

try this with quick sort... i think it is the best among the sorting techniques....