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..).

Questions by vipin gupta   answers by vipin gupta

Editorial / Best Answer

Answered by: David Rachutin

  • Dec 27th, 2006

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!

Showing Answers 1 - 68 of 68 Answers

vipin gupta

  • Dec 18th, 2006
 

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...

  Was this answer useful?  Yes

David Rachutin

  • Dec 27th, 2006
 

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!

jins

  • Jan 21st, 2007
 

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.

  Was this answer useful?  Yes

Guest

  • Mar 25th, 2007
 

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


          

  Was this answer useful?  Yes

mywing

  • Apr 27th, 2007
 

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?

  Was this answer useful?  Yes

TofuAvenger

  • May 23rd, 2007
 

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

  Was this answer useful?  Yes

purvid

  • Jun 3rd, 2007
 

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???  ...

  Was this answer useful?  Yes

TofuAvenger

  • Jun 5th, 2007
 

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 mywing?s 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, I?d 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 mywing?s 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). I?m still rooting for you, mywing. Please help us lesser intellectuals understand your wisdom here.

  Was this answer useful?  Yes

TofuAvenger

  • Jun 5th, 2007
 

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 doesn?t 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). Let?s 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 you?re thinking of negating each item in the list ? think again).

  Was this answer useful?  Yes

TofuAvenger

  • Jun 5th, 2007
 

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()


  Was this answer useful?  Yes

vandita

  • Jun 27th, 2007
 

//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 [:)]

  Was this answer useful?  Yes

TofuAvenger

  • Jun 27th, 2007
 

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.

  Was this answer useful?  Yes

Jasvinder

  • Jul 6th, 2007
 

here is my code

#include<iostream>
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";
    }
}

  Was this answer useful?  Yes

abhijeet

  • Jul 9th, 2007
 

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

}

  Was this answer useful?  Yes

TofuAvenger

  • Jul 9th, 2007
 

Jasvinder, nice idea! Too bad it?s 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.

  Was this answer useful?  Yes

TofuAvenger

  • Jul 9th, 2007
 

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 don?t 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 won?t overflow
your *SUPER* enormous variables.

Well, let?s try a test. Let?s 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 that?s 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 that?s 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 don?t 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 that?s 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 there?s no reason why your array can?t have
18,446,744,073,709,551,615 entries (except that it probably wouldn?t 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.



  Was this answer useful?  Yes

TofuAvenger

  • Jul 9th, 2007
 

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


Now that I?ve had time to fully examine it I?ve 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 didn?t 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 doesn?t understand
what integers are in 32 bit, 64 bit, or even 128 bit architectures.

  Was this answer useful?  Yes

connect

  • Jul 23rd, 2007
 

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

  Was this answer useful?  Yes

Jasvinder

  • Jul 24th, 2007
 

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

Jasvinder

  • Jul 24th, 2007
 

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.

  Was this answer useful?  Yes

TofuAvenger

  • Jul 24th, 2007
 

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). 

  Was this answer useful?  Yes

TofuAvenger

  • Jul 24th, 2007
 

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??

  Was this answer useful?  Yes

TofuAvenger

  • Jul 26th, 2007
 

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.

  Was this answer useful?  Yes

drmfslx

  • Aug 11th, 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 ??????? ++(*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).

  Was this answer useful?  Yes

suman Kasam

  • Sep 7th, 2007
 

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 by knowing 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.

  Was this answer useful?  Yes

sachin khaire

  • Nov 1st, 2007
 

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








  Was this answer useful?  Yes

Henry Korol

  • Nov 2nd, 2007
 

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.

  Was this answer useful?  Yes

Ravi Teja

  • Nov 14th, 2007
 

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

  Was this answer useful?  Yes

waqasabdul

  • Nov 28th, 2007
 


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<unsigned int>(pow(UINT_MAX, 0.5)) - 1)
       return -1;

   unsigned int ActualSum = 0;
   unsigned int ExpectedSum = (static_cast<unsigned int>(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;
}

  Was this answer useful?  Yes

waqasabdul

  • Nov 28th, 2007
 

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<unsigned int>(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.

  Was this answer useful?  Yes

waqasabdul

  • Dec 11th, 2007
 

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;

}

  Was this answer useful?  Yes

GildeD

  • Jan 28th, 2008
 

"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.

TofuAvenger

  • Jan 28th, 2008
 

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.

  Was this answer useful?  Yes

GildeD

  • Jan 28th, 2008
 

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.

Vishwas.p

  • Feb 8th, 2008
 

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




 

  Was this answer useful?  Yes

TofuAvenger

  • Feb 8th, 2008
 

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()


keeeg

  • Mar 8th, 2008
 

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

  Was this answer useful?  Yes

sskps

  • May 16th, 2008
 

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

  Was this answer useful?  Yes

klynch67

  • May 18th, 2008
 

# 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";

  Was this answer useful?  Yes

go_raja

  • May 20th, 2008
 

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

  Was this answer useful?  Yes

abhijitbh1979

  • May 23rd, 2008
 

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;

  Was this answer useful?  Yes

vids_spring

  • May 31st, 2008
 

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..

  Was this answer useful?  Yes

jca_dips

  • Jul 17th, 2008
 

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

}

  Was this answer useful?  Yes

pravash109

  • Jul 28th, 2008
 

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.

  Was this answer useful?  Yes

stevenxy

  • Aug 19th, 2008
 

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

  Was this answer useful?  Yes

rem132

  • Sep 2nd, 2008
 

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.

  Was this answer useful?  Yes

Sanjeet Kumar

  • Oct 26th, 2008
 

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).

  Was this answer useful?  Yes

adwiv

  • Nov 11th, 2008
 

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 :-)

  Was this answer useful?  Yes

ashpadhye

  • Oct 14th, 2009
 

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.

  Was this answer useful?  Yes

puzzlu

  • Sep 21st, 2010
 

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

  Was this answer useful?  Yes

helium3

  • Dec 19th, 2010
 

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

  Was this answer useful?  Yes

Sumit Khedkar

  • May 27th, 2011
 

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)!!!

  Was this answer useful?  Yes

pearls

  • Jul 15th, 2011
 

Here is the code for this 

Code
  1. #include<stdio.h>

    2. 

  2. #include<stdlib.h>

    3. 

  3. "enter the size of the array 

    4. 

  4. ");

    5. 

  5.  scanf("%d"// values stored in 1 to n for convinience !!!!"Enter the value .... should be between 1 and %d

    6. 

  6.  " , n );

    7. 

  7.         scanf("%d""%d value has been repeated...""%d value has been missing ", i);

    8. 

  8. }

  Was this answer useful?  Yes

anshul

  • Jul 30th, 2011
 

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

  Was this answer useful?  Yes

sachin

  • Aug 20th, 2011
 

Assume element m is repeated in place of p.

Code
  1.  


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

  Was this answer useful?  Yes

patoutthere

  • Aug 23rd, 2011
 

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

  Was this answer useful?  Yes

patoutthere

  • Oct 2nd, 2011
 

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
  1. span style="font-style: italic;">// i has already been found and thus set to 0

  Was this answer useful?  Yes

Chirag

  • Oct 11th, 2011
 

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

  Was this answer useful?  Yes

user

  • Oct 18th, 2011
 

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...

  Was this answer useful?  Yes

Alejandro Cons

  • Nov 9th, 2011
 

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
  1.         /// <summary>

    2. 

  2.         /// Finds the first/lowest duplicate and missing element in O(n) time

    3. 

  3.         /// Worst case scenario works in O(2n) but since constants are excluded from the O notation, it can be considered as O(n)

    4. 

  4.         /// </summary>

    5. 

  5.         /// <param name="A">Array of values 1 to N where N is the size of array</param>//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)//while the number on the position is not correct and the numbers to swap are different then swap//if the position i remains with a non-corresponding number and the numbers to swap 

    6. 

  6.                 //are the same then we have found our duplicate and missing elements//Display the result"No Duplicate found""Duplicate: " + duplicate);

    7. 

  7.                 Console.WriteLine("Missing: " + missing);

    8. 

  8.             }

    9. 

  9.         }

    10. 

  10.  

    11. 

  11.         /// <summary>

    12. 

  12.         /// Swaps 2 values by reference without using an aux variable

    13. 

  13.         /// </summary>

    14. 

  14.         /// <param name="a"></param>

    15. 

  15.         /// <param name="b"></param>

  Was this answer useful?  Yes

Naresh

  • Feb 22nd, 2012
 

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

  Was this answer useful?  Yes

Abhijit Samantaray

  • Mar 6th, 2012
 

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)

  Was this answer useful?  Yes

kaviya

  • Mar 12th, 2012
 

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

  Was this answer useful?  Yes

bakesh

  • Mar 16th, 2015
 

9

  Was this answer useful?  Yes

Gaurav.khurana

  • Apr 25th, 2015
 

@vandita Just a minor correction
i think we should go till n-1 only so the in for loop it should be and should use i+1 since nbrs are starting from 1 and not 0

Code
  1. span style="font-style: italic;">//since 1 is stored at 0th position

  Was this answer useful?  Yes

Give your answer:

If you think the above answer is not correct, Please select a reason and add your answer below.

 

Related Answered Questions

 

Related Open Questions