Re: [algogeeks] Re: find duplicate and missing element

[Raj Jagvanshi]

@ashish aggarwal
good solution
but my problem is
ex.
i have n array of element 1,2,3,3,4;
XOR of (1,2,3,3,4)with (1,2,3,4,5). finally i have
XOR of 3 nd 5 (3^5) is 110

now what
pls explan me in detail
On Thu, Sep 2, 2010 at 1:30 PM, ashish agarwal  wrote:

> In this method overflow will be there..if number is just bigger...so by
> doing XOR we can get missing number and repeated number .
> take xor of all element of array and take this xor with array[1...n]
> So we get xor of two numbers.
> now get set bit of this xor and proceed.
>
> On Thu, Sep 2, 2010 at 12:36 AM, bittu  wrote:
>
>> @luckyzoner
>>
>>  can post the c program of what u ave said above..
>>
>> --
>> You received this message because you are subscribed to the Google Groups
>> "Algorithm Geeks" group.
>> To post to this group, send email to algoge...@googlegroups.com.
>> To unsubscribe from this group, send email to
>> algogeeks+unsubscr...@googlegroups.com
>> .
>> For more options, visit this group at
>> http://groups.google.com/group/algogeeks?hl=en.
>>
>>
>  --
> You received this message because you are subscribed to the Google Groups
> "Algorithm Geeks" group.
> To post to this group, send email to algoge...@googlegroups.com.
> To unsubscribe from this group, send email to
> algogeeks+unsubscr...@googlegroups.com
> .
> For more options, visit this group at
> http://groups.google.com/group/algogeeks?hl=en.
>

-- 
You received this message because you are subscribed to the Google Groups 
"Algorithm Geeks" group.
To post to this group, send email to algoge...@googlegroups.com.
To unsubscribe from this group, send email to 
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at 
http://groups.google.com/group/algogeeks?hl=en.

[algogeeks] Re: find duplicate and missing element

[bittu]

what do u think about this ...its O(n) program..


#include
#include
# include "malloc.h"
# include 


bool bRemoveDuplicates(int array[], int iSize){
  if(iSize <1)
  return false;
  if(array == NULL)
return false;
  if(iSize == 1)
return true;

  int left_comp = 0;
  int right_comp = 1;
  bool start_move = false;
  int flag=0;
  int hole =0;

//{1,1,1,1,1,1,1,1,2,2,4,5,7,8,8,9,9,10,11,11,12,13,14};

  for(; right_comp >i;

}

-- 
You received this message because you are subscribed to the Google Groups 
"Algorithm Geeks" group.
To post to this group, send email to algoge...@googlegroups.com.
To unsubscribe from this group, send email to 
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at 
http://groups.google.com/group/algogeeks?hl=en.

Re: [algogeeks] Re: find duplicate and missing element

[kartheek muthyala]

@ankit

Yup I got your point. I didn't see the algo given by dhritiman previously. I
think that is better than my solution , where it fits in all cases.


Cheers
Kartheek

On Fri, Sep 3, 2010 at 1:32 PM, Ankit Sinha  wrote:

> @kartheek, thanks for ur input!! Certainly, ur soln is fine but only
> will cater when array is 1...n but what if it ranges for 0...n-1. The
> algo given by dhritiman fits in all the scenario. but ofcourse for
> given question ( 1 to 100) your mathematical approach is good. :)...
>
> Cheers,
> Ankit Sinha!!!
>
> On Fri, Sep 3, 2010 at 8:14 AM, kartheek muthyala
>  wrote:y
> >
> > Yeah
> > The solution given by Ankit is gr8. But inorder to not destroy the array
> we
> > need to go by the geek method where
> >
> > Suppose x is the duplicated element and y is the missing element in the
> > array.
> > Multiply all the elements in the array to prod and sum all the elements
> in
> > the array to sum.
> > Divide prod with 100! that is gonna give value of x/y
> > Subtract sum from 5050 that is gonna give 5050 + x - y
> > Solve the two equations to get x and y.
> > It is gonna take O(N) ideally.
> > Cheers
> >  Kartheek
> >
> > On Fri, Sep 3, 2010 at 11:09 AM, Ankit Sinha 
> wrote:
> >>
> >> @Dhritiman, It's good algo man!!!The only thing is we are destroying
> >> the array but also that's mandatory as only o(n) complexity we are
> >> interested in.
> >>
> >> As Somebody wanted the code, here I am attaching below: -
> >>
> >>   int a[SIZE_A] = {0,2,1,4,0};
> >>   int i = 0, dup = 0, pos = 0, t =0;
> >>   while (i< 5)
> >>   {
> >>   if (a[i] == i)
> >>   i++;
> >>   else if (a[a[i]] == a[i])
> >>   {
> >>   dup = a[i];
> >>
> >>   printf ("\nduplicated element is [%d]", dup);
> >>   pos = i;
> >>   i++;
> >>   }
> >>   else
> >>   {
> >>   t= a[i];
> >>   a[i] =  a[a[i]];
> >>   a[t] = t;
> >>   }
> >>   }
> >>   printf ("\nmissing element is [%d]", pos);
> >>
> >>
> >> Cheers,
> >> Ankit Sinha
> >>
> >> On Thu, Sep 2, 2010 at 7:08 AM, Dhritiman Das 
> >> wrote:
> >> > @Dinesh,
> >> > Yes, we can't apply this method, if that's not allowed.
> >> >
> >> > On Thu, Sep 2, 2010 at 10:31 AM, dinesh bansal 
> >> > wrote:
> >> >>
> >> >>
> >> >> On Wed, Sep 1, 2010 at 11:08 AM, Dhritiman Das <
> dedhriti...@gmail.com>
> >> >> wrote:
> >> >>>
> >> >>> Given a array, A[1..n], do the following.
> >> >>> Start from i=1 and try placing each number in its correct position
> in
> >> >>> the
> >> >>> array.
> >> >>> If the number is already in its correct position, go ahead. if (A[i]
> >> >>> ==
> >> >>> i) , i++
> >> >>> else if the number was already restored to its correct position,
> then
> >> >>> it
> >> >>> is
> >> >>> a duplicate , so remember it and move ahead if (A[A[i]] == A[i]),
> dup
> >> >>> =
> >> >>> A[i], i++ ;
> >> >>> else
> >> >>>   swap the elements at the current index i and that at A[i]'s
> correct
> >> >>> position in the array.
> >> >>> continue this until all numbers are placed in their correct position
> >> >>> in
> >> >>> the array
> >> >>> Finally, A[missing] will be dup.
> >> >>> O(n)
> >> >>
> >> >>
> >> >> @Dharitiman, good solution man. No expensive computation, no extra
> >> >> memory
> >> >> required. Only problem is it will change the input array to sorted
> >> >> order
> >> >> which may not be desired.
> >> >>
> >> >>>
> >> >>> On Wed, Sep 1, 2010 at 7:14 AM, Dave 
> wrote:
> >> 
> >>  Suppose that x is duplicated and y is omitted. Then the sum of the
> >>  numbers would be 5050 + x - y. Similarly, the sums of the squares
> of
> >>  the numbers would be 338,350 + x^2 - y^2. Calculate the sum and sum
> >>  of
> >>  squares of the numbers and solve the resulting equations for x and
> y.
> >> 
> >>  Dave
> >> 
> >>  On Aug 31, 1:57 pm, Raj Jagvanshi  wrote:
> >>  >   There is an array having distinct 100 elements from 1 to 100
> >>  >  but by mistake some no is duplicated and a no is missed.
> >>  >  Find the duplicate no and missing no.
> >>  >
> >>  > Thanks
> >>  > Raj Jagvanshi
> >> 
> >>  --
> >>  You received this message because you are subscribed to the Google
> >>  Groups "Algorithm Geeks" group.
> >>  To post to this group, send email to algoge...@googlegroups.com.
> >>  To unsubscribe from this group, send email to
> >>  algogeeks+unsubscr...@googlegroups.com
> .
> >>  For more options, visit this group at
> >>  http://groups.google.com/group/algogeeks?hl=en.
> >> 
> >> >>>
> >> >>> --
> >> >>> You received this message because you are subscribed to the Google
> >> >>> Groups
> >> >>> "Algorithm Geeks" group.
> >> >>> To post to this group, send email to algoge...@googlegroups

Re: [algogeeks] Re: find duplicate and missing element

[Ankit Sinha]

@kartheek, thanks for ur input!! Certainly, ur soln is fine but only
will cater when array is 1...n but what if it ranges for 0...n-1. The
algo given by dhritiman fits in all the scenario. but ofcourse for
given question ( 1 to 100) your mathematical approach is good. :)...

Cheers,
Ankit Sinha!!!

On Fri, Sep 3, 2010 at 8:14 AM, kartheek muthyala
 wrote:y
>
> Yeah
> The solution given by Ankit is gr8. But inorder to not destroy the array we
> need to go by the geek method where
>
> Suppose x is the duplicated element and y is the missing element in the
> array.
> Multiply all the elements in the array to prod and sum all the elements in
> the array to sum.
> Divide prod with 100! that is gonna give value of x/y
> Subtract sum from 5050 that is gonna give 5050 + x - y
> Solve the two equations to get x and y.
> It is gonna take O(N) ideally.
> Cheers
>  Kartheek
>
> On Fri, Sep 3, 2010 at 11:09 AM, Ankit Sinha  wrote:
>>
>> @Dhritiman, It's good algo man!!!The only thing is we are destroying
>> the array but also that's mandatory as only o(n) complexity we are
>> interested in.
>>
>> As Somebody wanted the code, here I am attaching below: -
>>
>>       int a[SIZE_A] = {0,2,1,4,0};
>>       int i = 0, dup = 0, pos = 0, t =0;
>>       while (i< 5)
>>       {
>>               if (a[i] == i)
>>                       i++;
>>               else if (a[a[i]] == a[i])
>>               {
>>                               dup = a[i];
>>
>>                   printf ("\nduplicated element is [%d]", dup);
>>                               pos = i;
>>                               i++;
>>               }
>>               else
>>               {
>>                       t= a[i];
>>                       a[i] =  a[a[i]];
>>                       a[t] = t;
>>               }
>>       }
>>       printf ("\nmissing element is [%d]", pos);
>>
>>
>> Cheers,
>> Ankit Sinha
>>
>> On Thu, Sep 2, 2010 at 7:08 AM, Dhritiman Das 
>> wrote:
>> > @Dinesh,
>> > Yes, we can't apply this method, if that's not allowed.
>> >
>> > On Thu, Sep 2, 2010 at 10:31 AM, dinesh bansal 
>> > wrote:
>> >>
>> >>
>> >> On Wed, Sep 1, 2010 at 11:08 AM, Dhritiman Das 
>> >> wrote:
>> >>>
>> >>> Given a array, A[1..n], do the following.
>> >>> Start from i=1 and try placing each number in its correct position in
>> >>> the
>> >>> array.
>> >>> If the number is already in its correct position, go ahead. if (A[i]
>> >>> ==
>> >>> i) , i++
>> >>> else if the number was already restored to its correct position, then
>> >>> it
>> >>> is
>> >>> a duplicate , so remember it and move ahead if (A[A[i]] == A[i]), dup
>> >>> =
>> >>> A[i], i++ ;
>> >>> else
>> >>>   swap the elements at the current index i and that at A[i]'s correct
>> >>> position in the array.
>> >>> continue this until all numbers are placed in their correct position
>> >>> in
>> >>> the array
>> >>> Finally, A[missing] will be dup.
>> >>> O(n)
>> >>
>> >>
>> >> @Dharitiman, good solution man. No expensive computation, no extra
>> >> memory
>> >> required. Only problem is it will change the input array to sorted
>> >> order
>> >> which may not be desired.
>> >>
>> >>>
>> >>> On Wed, Sep 1, 2010 at 7:14 AM, Dave  wrote:
>> 
>>  Suppose that x is duplicated and y is omitted. Then the sum of the
>>  numbers would be 5050 + x - y. Similarly, the sums of the squares of
>>  the numbers would be 338,350 + x^2 - y^2. Calculate the sum and sum
>>  of
>>  squares of the numbers and solve the resulting equations for x and y.
>> 
>>  Dave
>> 
>>  On Aug 31, 1:57 pm, Raj Jagvanshi  wrote:
>>  >   There is an array having distinct 100 elements from 1 to 100
>>  >  but by mistake some no is duplicated and a no is missed.
>>  >  Find the duplicate no and missing no.
>>  >
>>  > Thanks
>>  > Raj Jagvanshi
>> 
>>  --
>>  You received this message because you are subscribed to the Google
>>  Groups "Algorithm Geeks" group.
>>  To post to this group, send email to algoge...@googlegroups.com.
>>  To unsubscribe from this group, send email to
>>  algogeeks+unsubscr...@googlegroups.com.
>>  For more options, visit this group at
>>  http://groups.google.com/group/algogeeks?hl=en.
>> 
>> >>>
>> >>> --
>> >>> You received this message because you are subscribed to the Google
>> >>> Groups
>> >>> "Algorithm Geeks" group.
>> >>> To post to this group, send email to algoge...@googlegroups.com.
>> >>> To unsubscribe from this group, send email to
>> >>> algogeeks+unsubscr...@googlegroups.com.
>> >>> For more options, visit this group at
>> >>> http://groups.google.com/group/algogeeks?hl=en.
>> >>
>> >>
>> >>
>> >> --
>> >> Dinesh Bansal
>> >> The Law of Win says, "Let's not do it your way or my way; let's do it
>> >> the
>> >> best way."
>> >>
>> >> --
>> >> You received this message because you are subscribed to the Google
>> >> Groups
>> >> "Algorithm Geeks" group.
>> >> To post to this group, send email to algoge...@goo

Re: [algogeeks] Re: find duplicate and missing element

[kartheek muthyala]

Yeah

The solution given by Ankit is gr8. But inorder to not destroy the array we
need to go by the geek method where


Suppose x is the duplicated element and y is the missing element in the
array.

Multiply all the elements in the array to prod and sum all the elements in
the array to sum.

Divide prod with 100! that is gonna give value of x/y
Subtract sum from 5050 that is gonna give 5050 + x - y

Solve the two equations to get x and y.

It is gonna take O(N) ideally.

Cheers
 Kartheek


On Fri, Sep 3, 2010 at 11:09 AM, Ankit Sinha  wrote:

> @Dhritiman, It's good algo man!!!The only thing is we are destroying
> the array but also that's mandatory as only o(n) complexity we are
> interested in.
>
> As Somebody wanted the code, here I am attaching below: -
>
>   int a[SIZE_A] = {0,2,1,4,0};
>   int i = 0, dup = 0, pos = 0, t =0;
>   while (i< 5)
>   {
>   if (a[i] == i)
>   i++;
>   else if (a[a[i]] == a[i])
>   {
>   dup = a[i];
>
>   printf ("\nduplicated element is [%d]", dup);
>   pos = i;
>   i++;
>   }
>   else
>   {
>   t= a[i];
>   a[i] =  a[a[i]];
>   a[t] = t;
>   }
>   }
>   printf ("\nmissing element is [%d]", pos);
>
>
> Cheers,
> Ankit Sinha
>
> On Thu, Sep 2, 2010 at 7:08 AM, Dhritiman Das 
> wrote:
> > @Dinesh,
> > Yes, we can't apply this method, if that's not allowed.
> >
> > On Thu, Sep 2, 2010 at 10:31 AM, dinesh bansal 
> wrote:
> >>
> >>
> >> On Wed, Sep 1, 2010 at 11:08 AM, Dhritiman Das 
> >> wrote:
> >>>
> >>> Given a array, A[1..n], do the following.
> >>> Start from i=1 and try placing each number in its correct position in
> the
> >>> array.
> >>> If the number is already in its correct position, go ahead. if (A[i] ==
> >>> i) , i++
> >>> else if the number was already restored to its correct position, then
> it
> >>> is
> >>> a duplicate , so remember it and move ahead if (A[A[i]] == A[i]), dup =
> >>> A[i], i++ ;
> >>> else
> >>>   swap the elements at the current index i and that at A[i]'s correct
> >>> position in the array.
> >>> continue this until all numbers are placed in their correct position in
> >>> the array
> >>> Finally, A[missing] will be dup.
> >>> O(n)
> >>
> >>
> >> @Dharitiman, good solution man. No expensive computation, no extra
> memory
> >> required. Only problem is it will change the input array to sorted order
> >> which may not be desired.
> >>
> >>>
> >>> On Wed, Sep 1, 2010 at 7:14 AM, Dave  wrote:
> 
>  Suppose that x is duplicated and y is omitted. Then the sum of the
>  numbers would be 5050 + x - y. Similarly, the sums of the squares of
>  the numbers would be 338,350 + x^2 - y^2. Calculate the sum and sum of
>  squares of the numbers and solve the resulting equations for x and y.
> 
>  Dave
> 
>  On Aug 31, 1:57 pm, Raj Jagvanshi  wrote:
>  >   There is an array having distinct 100 elements from 1 to 100
>  >  but by mistake some no is duplicated and a no is missed.
>  >  Find the duplicate no and missing no.
>  >
>  > Thanks
>  > Raj Jagvanshi
> 
>  --
>  You received this message because you are subscribed to the Google
>  Groups "Algorithm Geeks" group.
>  To post to this group, send email to algoge...@googlegroups.com.
>  To unsubscribe from this group, send email to
>  algogeeks+unsubscr...@googlegroups.com
> .
>  For more options, visit this group at
>  http://groups.google.com/group/algogeeks?hl=en.
> 
> >>>
> >>> --
> >>> You received this message because you are subscribed to the Google
> Groups
> >>> "Algorithm Geeks" group.
> >>> To post to this group, send email to algoge...@googlegroups.com.
> >>> To unsubscribe from this group, send email to
> >>> algogeeks+unsubscr...@googlegroups.com
> .
> >>> For more options, visit this group at
> >>> http://groups.google.com/group/algogeeks?hl=en.
> >>
> >>
> >>
> >> --
> >> Dinesh Bansal
> >> The Law of Win says, "Let's not do it your way or my way; let's do it
> the
> >> best way."
> >>
> >> --
> >> You received this message because you are subscribed to the Google
> Groups
> >> "Algorithm Geeks" group.
> >> To post to this group, send email to algoge...@googlegroups.com.
> >> To unsubscribe from this group, send email to
> >> algogeeks+unsubscr...@googlegroups.com
> .
> >> For more options, visit this group at
> >> http://groups.google.com/group/algogeeks?hl=en.
> >
> > --
> > You received this message because you are subscribed to the Google Groups
> > "Algorithm Geeks" group.
> > To post to this group, send email to algoge...@googlegroups.com.
> > To unsubscribe from this group, send email to
> > algogeeks+unsubscr...@googlegroups.com
> .
> > For more options, visit this group at
> > http://groups.goog

Re: [algogeeks] Re: find duplicate and missing element

[Ankit Sinha]

@Dhritiman, It's good algo man!!!The only thing is we are destroying
the array but also that's mandatory as only o(n) complexity we are
interested in.

As Somebody wanted the code, here I am attaching below: -

   int a[SIZE_A] = {0,2,1,4,0};
   int i = 0, dup = 0, pos = 0, t =0;
   while (i< 5)
   {
   if (a[i] == i)
   i++;
   else if (a[a[i]] == a[i])
   {
   dup = a[i];

   printf ("\nduplicated element is [%d]", dup);
   pos = i;
   i++;
   }
   else
   {
   t= a[i];
   a[i] =  a[a[i]];
   a[t] = t;
   }
   }
   printf ("\nmissing element is [%d]", pos);


Cheers,
Ankit Sinha

On Thu, Sep 2, 2010 at 7:08 AM, Dhritiman Das  wrote:
> @Dinesh,
> Yes, we can't apply this method, if that's not allowed.
>
> On Thu, Sep 2, 2010 at 10:31 AM, dinesh bansal  wrote:
>>
>>
>> On Wed, Sep 1, 2010 at 11:08 AM, Dhritiman Das 
>> wrote:
>>>
>>> Given a array, A[1..n], do the following.
>>> Start from i=1 and try placing each number in its correct position in the
>>> array.
>>> If the number is already in its correct position, go ahead. if (A[i] ==
>>> i) , i++
>>> else if the number was already restored to its correct position, then it
>>> is
>>> a duplicate , so remember it and move ahead if (A[A[i]] == A[i]), dup =
>>> A[i], i++ ;
>>> else
>>>   swap the elements at the current index i and that at A[i]'s correct
>>> position in the array.
>>> continue this until all numbers are placed in their correct position in
>>> the array
>>> Finally, A[missing] will be dup.
>>> O(n)
>>
>>
>> @Dharitiman, good solution man. No expensive computation, no extra memory
>> required. Only problem is it will change the input array to sorted order
>> which may not be desired.
>>
>>>
>>> On Wed, Sep 1, 2010 at 7:14 AM, Dave  wrote:

 Suppose that x is duplicated and y is omitted. Then the sum of the
 numbers would be 5050 + x - y. Similarly, the sums of the squares of
 the numbers would be 338,350 + x^2 - y^2. Calculate the sum and sum of
 squares of the numbers and solve the resulting equations for x and y.

 Dave

 On Aug 31, 1:57 pm, Raj Jagvanshi  wrote:
 >   There is an array having distinct 100 elements from 1 to 100
 >  but by mistake some no is duplicated and a no is missed.
 >  Find the duplicate no and missing no.
 >
 > Thanks
 > Raj Jagvanshi

 --
 You received this message because you are subscribed to the Google
 Groups "Algorithm Geeks" group.
 To post to this group, send email to algoge...@googlegroups.com.
 To unsubscribe from this group, send email to
 algogeeks+unsubscr...@googlegroups.com.
 For more options, visit this group at
 http://groups.google.com/group/algogeeks?hl=en.

>>>
>>> --
>>> You received this message because you are subscribed to the Google Groups
>>> "Algorithm Geeks" group.
>>> To post to this group, send email to algoge...@googlegroups.com.
>>> To unsubscribe from this group, send email to
>>> algogeeks+unsubscr...@googlegroups.com.
>>> For more options, visit this group at
>>> http://groups.google.com/group/algogeeks?hl=en.
>>
>>
>>
>> --
>> Dinesh Bansal
>> The Law of Win says, "Let's not do it your way or my way; let's do it the
>> best way."
>>
>> --
>> You received this message because you are subscribed to the Google Groups
>> "Algorithm Geeks" group.
>> To post to this group, send email to algoge...@googlegroups.com.
>> To unsubscribe from this group, send email to
>> algogeeks+unsubscr...@googlegroups.com.
>> For more options, visit this group at
>> http://groups.google.com/group/algogeeks?hl=en.
>
> --
> You received this message because you are subscribed to the Google Groups
> "Algorithm Geeks" group.
> To post to this group, send email to algoge...@googlegroups.com.
> To unsubscribe from this group, send email to
> algogeeks+unsubscr...@googlegroups.com.
> For more options, visit this group at
> http://groups.google.com/group/algogeeks?hl=en.
>

-- 
You received this message because you are subscribed to the Google Groups 
"Algorithm Geeks" group.
To post to this group, send email to algoge...@googlegroups.com.
To unsubscribe from this group, send email to 
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at 
http://groups.google.com/group/algogeeks?hl=en.

Re: [algogeeks] Re: find duplicate and missing element

[Manjunath Manohar]

this question can be sovled very easily

1.jus sum the given array...x
2.sum the squares of the given array..y
3.now use the AP.n(n+1)/2..for n=100
4.similarly compute n(n+1)(2n+1)/6 for n =100..

Now solve these eqns ...u get the missing and the dupicate..

-- 
You received this message because you are subscribed to the Google Groups 
"Algorithm Geeks" group.
To post to this group, send email to algoge...@googlegroups.com.
To unsubscribe from this group, send email to 
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at 
http://groups.google.com/group/algogeeks?hl=en.

Re: [algogeeks] Re: find duplicate and missing element

[vikash jain]

@ashish:  cud u plzz explain a bit more...

-- 
You received this message because you are subscribed to the Google Groups 
"Algorithm Geeks" group.
To post to this group, send email to algoge...@googlegroups.com.
To unsubscribe from this group, send email to 
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at 
http://groups.google.com/group/algogeeks?hl=en.

Re: [algogeeks] Re: find duplicate and missing element

[ashish agarwal]

In this method overflow will be there..if number is just bigger...so by
doing XOR we can get missing number and repeated number .
take xor of all element of array and take this xor with array[1...n]
So we get xor of two numbers.
now get set bit of this xor and proceed.

On Thu, Sep 2, 2010 at 12:36 AM, bittu  wrote:

> @luckyzoner
>
>  can post the c program of what u ave said above..
>
> --
> You received this message because you are subscribed to the Google Groups
> "Algorithm Geeks" group.
> To post to this group, send email to algoge...@googlegroups.com.
> To unsubscribe from this group, send email to
> algogeeks+unsubscr...@googlegroups.com
> .
> For more options, visit this group at
> http://groups.google.com/group/algogeeks?hl=en.
>
>

-- 
You received this message because you are subscribed to the Google Groups 
"Algorithm Geeks" group.
To post to this group, send email to algoge...@googlegroups.com.
To unsubscribe from this group, send email to 
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at 
http://groups.google.com/group/algogeeks?hl=en.

[algogeeks] Re: find duplicate and missing element

[bittu]

@luckyzoner

 can post the c program of what u ave said above..

-- 
You received this message because you are subscribed to the Google Groups 
"Algorithm Geeks" group.
To post to this group, send email to algoge...@googlegroups.com.
To unsubscribe from this group, send email to 
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at 
http://groups.google.com/group/algogeeks?hl=en.

Re: [algogeeks] Re: find duplicate and missing element

[Dhritiman Das]

@Dinesh,
Yes, we can't apply this method, if that's not allowed.

On Thu, Sep 2, 2010 at 10:31 AM, dinesh bansal  wrote:

>
>
> On Wed, Sep 1, 2010 at 11:08 AM, Dhritiman Das wrote:
>
>>
>> Given a array, A[1..n], do the following.
>> Start from i=1 and try placing each number in its correct position in the
>> array.
>> If the number is already in its correct position, go ahead. if (A[i] == i)
>> , i++
>> else if the number was already restored to its correct position, then it
>> is
>> a duplicate , so remember it and move ahead if (A[A[i]] == A[i]), dup =
>> A[i], i++ ;
>> else
>>   swap the elements at the current index i and that at A[i]'s correct
>> position in the array.
>> continue this until all numbers are placed in their correct position in
>> the array
>> Finally, A[missing] will be dup.
>> O(n)
>>
>>
> *...@dharitiman, good solution man. No expensive computation, no extra memory
> required. Only problem is it will change the input array to sorted order
> which may not be desired. *
>
>
>> On Wed, Sep 1, 2010 at 7:14 AM, Dave  wrote:
>>
>>> Suppose that x is duplicated and y is omitted. Then the sum of the
>>> numbers would be 5050 + x - y. Similarly, the sums of the squares of
>>> the numbers would be 338,350 + x^2 - y^2. Calculate the sum and sum of
>>> squares of the numbers and solve the resulting equations for x and y.
>>>
>>> Dave
>>>
>>> On Aug 31, 1:57 pm, Raj Jagvanshi  wrote:
>>> >   There is an array having distinct 100 elements from 1 to 100
>>> >  but by mistake some no is duplicated and a no is missed.
>>> >  Find the duplicate no and missing no.
>>> >
>>> > Thanks
>>> > Raj Jagvanshi
>>>
>>> --
>>> You received this message because you are subscribed to the Google Groups
>>> "Algorithm Geeks" group.
>>> To post to this group, send email to algoge...@googlegroups.com.
>>> To unsubscribe from this group, send email to
>>> algogeeks+unsubscr...@googlegroups.com
>>> .
>>> For more options, visit this group at
>>> http://groups.google.com/group/algogeeks?hl=en.
>>>
>>>
>>  --
>> You received this message because you are subscribed to the Google Groups
>> "Algorithm Geeks" group.
>> To post to this group, send email to algoge...@googlegroups.com.
>> To unsubscribe from this group, send email to
>> algogeeks+unsubscr...@googlegroups.com
>> .
>> For more options, visit this group at
>> http://groups.google.com/group/algogeeks?hl=en.
>>
>
>
>
> --
> Dinesh Bansal
> The Law of Win says, "Let's not do it your way or my way; let's do it the
> best way."
>
> --
> You received this message because you are subscribed to the Google Groups
> "Algorithm Geeks" group.
> To post to this group, send email to algoge...@googlegroups.com.
> To unsubscribe from this group, send email to
> algogeeks+unsubscr...@googlegroups.com
> .
> For more options, visit this group at
> http://groups.google.com/group/algogeeks?hl=en.
>

-- 
You received this message because you are subscribed to the Google Groups 
"Algorithm Geeks" group.
To post to this group, send email to algoge...@googlegroups.com.
To unsubscribe from this group, send email to 
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at 
http://groups.google.com/group/algogeeks?hl=en.

Re: [algogeeks] Re: find duplicate and missing element

[dinesh bansal]

On Wed, Sep 1, 2010 at 11:08 AM, Dhritiman Das wrote:

>
> Given a array, A[1..n], do the following.
> Start from i=1 and try placing each number in its correct position in the
> array.
> If the number is already in its correct position, go ahead. if (A[i] == i)
> , i++
> else if the number was already restored to its correct position, then it is
> a duplicate , so remember it and move ahead if (A[A[i]] == A[i]), dup =
> A[i], i++ ;
> else
>   swap the elements at the current index i and that at A[i]'s correct
> position in the array.
> continue this until all numbers are placed in their correct position in the
> array
> Finally, A[missing] will be dup.
> O(n)
>
>
*...@dharitiman, good solution man. No expensive computation, no extra memory
required. Only problem is it will change the input array to sorted order
which may not be desired. *


> On Wed, Sep 1, 2010 at 7:14 AM, Dave  wrote:
>
>> Suppose that x is duplicated and y is omitted. Then the sum of the
>> numbers would be 5050 + x - y. Similarly, the sums of the squares of
>> the numbers would be 338,350 + x^2 - y^2. Calculate the sum and sum of
>> squares of the numbers and solve the resulting equations for x and y.
>>
>> Dave
>>
>> On Aug 31, 1:57 pm, Raj Jagvanshi  wrote:
>> >   There is an array having distinct 100 elements from 1 to 100
>> >  but by mistake some no is duplicated and a no is missed.
>> >  Find the duplicate no and missing no.
>> >
>> > Thanks
>> > Raj Jagvanshi
>>
>> --
>> You received this message because you are subscribed to the Google Groups
>> "Algorithm Geeks" group.
>> To post to this group, send email to algoge...@googlegroups.com.
>> To unsubscribe from this group, send email to
>> algogeeks+unsubscr...@googlegroups.com
>> .
>> For more options, visit this group at
>> http://groups.google.com/group/algogeeks?hl=en.
>>
>>
>  --
> You received this message because you are subscribed to the Google Groups
> "Algorithm Geeks" group.
> To post to this group, send email to algoge...@googlegroups.com.
> To unsubscribe from this group, send email to
> algogeeks+unsubscr...@googlegroups.com
> .
> For more options, visit this group at
> http://groups.google.com/group/algogeeks?hl=en.
>



-- 
Dinesh Bansal
The Law of Win says, "Let's not do it your way or my way; let's do it the
best way."

-- 
You received this message because you are subscribed to the Google Groups 
"Algorithm Geeks" group.
To post to this group, send email to algoge...@googlegroups.com.
To unsubscribe from this group, send email to 
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at 
http://groups.google.com/group/algogeeks?hl=en.

[algogeeks] Re: find duplicate and missing element

[Dave]

@Raj: It is just algebra.

Dave

On Sep 1, 11:50 am, Raj Jagvanshi  wrote:
> in ur algo i confuse in solving eqn
>
>
>
> On Wed, Sep 1, 2010 at 6:31 PM, Dave  wrote:
> > @Raj: Best what?
>
> > Dave
>
> > On Sep 1, 12:08 am, Raj Jagvanshi  wrote:
> > > Thanks Dave
> > > but i want best
>
> > > On Wed, Sep 1, 2010 at 7:14 AM, Dave  wrote:
> > > > Suppose that x is duplicated and y is omitted. Then the sum of the
> > > > numbers would be 5050 + x - y. Similarly, the sums of the squares of
> > > > the numbers would be 338,350 + x^2 - y^2. Calculate the sum and sum of
> > > > squares of the numbers and solve the resulting equations for x and y.
>
> > > > Dave
>
> > > > On Aug 31, 1:57 pm, Raj Jagvanshi  wrote:
> > > > >   There is an array having distinct 100 elements from 1 to 100
> > > > >  but by mistake some no is duplicated and a no is missed.
> > > > >  Find the duplicate no and missing no.
>
> > > > > Thanks
> > > > > Raj Jagvanshi
>
> > > > --
> > > > You received this message because you are subscribed to the Google
> > Groups
> > > > "Algorithm Geeks" group.
> > > > To post to this group, send email to algoge...@googlegroups.com.
> > > > To unsubscribe from this group, send email to
> > > > algogeeks+unsubscr...@googlegroups.com
> > 
> > > > .
> > > > For more options, visit this group at
> > > >http://groups.google.com/group/algogeeks?hl=en.-Hide quoted text -
>
> > > - Show quoted text -
>
> > --
> > You received this message because you are subscribed to the Google Groups
> > "Algorithm Geeks" group.
> > To post to this group, send email to algoge...@googlegroups.com.
> > To unsubscribe from this group, send email to
> > algogeeks+unsubscr...@googlegroups.com
> > .
> > For more options, visit this group at
> >http://groups.google.com/group/algogeeks?hl=en.- Hide quoted text -
>
> - Show quoted text -

-- 
You received this message because you are subscribed to the Google Groups 
"Algorithm Geeks" group.
To post to this group, send email to algoge...@googlegroups.com.
To unsubscribe from this group, send email to 
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at 
http://groups.google.com/group/algogeeks?hl=en.

[algogeeks] Re: find duplicate and missing element

[luckyzoner]

According to me we can apply the equatin method :

Let the missing number be y.
Let the duplicated no. be x.

1. then find the product of the 1 to 100 and the sum 1 to 100 :A
   Product would be of the form...1 *2*3x*..y*100 : B
   Sum : 1+2+3.+x+y.+100

2. find the prduct of array elements : P
   find the sum of array elemnts : S

3.  then A/P = y/x
 B-S = y-x

   Now solve the equations

-- 
You received this message because you are subscribed to the Google Groups 
"Algorithm Geeks" group.
To post to this group, send email to algoge...@googlegroups.com.
To unsubscribe from this group, send email to 
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at 
http://groups.google.com/group/algogeeks?hl=en.

Re: [algogeeks] Re: find duplicate and missing element

[Anand]

1. First find the sum of all given elements.: sum
2. find the sum of elements in the given range. : sum_1
3. Find the duplicates.: d
4. Missing Number: sum-sum_1+d.

http://codepad.org/77Nr9Hay



On Wed, Sep 1, 2010 at 9:50 AM, Raj Jagvanshi wrote:

> in ur algo i confuse in solving eqn
>
>
> On Wed, Sep 1, 2010 at 6:31 PM, Dave  wrote:
>
>> @Raj: Best what?
>>
>> Dave
>>
>> On Sep 1, 12:08 am, Raj Jagvanshi  wrote:
>> > Thanks Dave
>> > but i want best
>> >
>> >
>> >
>> > On Wed, Sep 1, 2010 at 7:14 AM, Dave  wrote:
>> > > Suppose that x is duplicated and y is omitted. Then the sum of the
>> > > numbers would be 5050 + x - y. Similarly, the sums of the squares of
>> > > the numbers would be 338,350 + x^2 - y^2. Calculate the sum and sum of
>> > > squares of the numbers and solve the resulting equations for x and y.
>> >
>> > > Dave
>> >
>> > > On Aug 31, 1:57 pm, Raj Jagvanshi  wrote:
>> > > >   There is an array having distinct 100 elements from 1 to 100
>> > > >  but by mistake some no is duplicated and a no is missed.
>> > > >  Find the duplicate no and missing no.
>> >
>> > > > Thanks
>> > > > Raj Jagvanshi
>> >
>> > > --
>> > > You received this message because you are subscribed to the Google
>> Groups
>> > > "Algorithm Geeks" group.
>> > > To post to this group, send email to algoge...@googlegroups.com.
>> > > To unsubscribe from this group, send email to
>> > > algogeeks+unsubscr...@googlegroups.com
>> 
>> > > .
>> > > For more options, visit this group at
>> > >http://groups.google.com/group/algogeeks?hl=en.- Hide quoted text -
>> >
>> > - Show quoted text -
>>
>> --
>> You received this message because you are subscribed to the Google Groups
>> "Algorithm Geeks" group.
>> To post to this group, send email to algoge...@googlegroups.com.
>> To unsubscribe from this group, send email to
>> algogeeks+unsubscr...@googlegroups.com
>> .
>> For more options, visit this group at
>> http://groups.google.com/group/algogeeks?hl=en.
>>
>>
>  --
> You received this message because you are subscribed to the Google Groups
> "Algorithm Geeks" group.
> To post to this group, send email to algoge...@googlegroups.com.
> To unsubscribe from this group, send email to
> algogeeks+unsubscr...@googlegroups.com
> .
> For more options, visit this group at
> http://groups.google.com/group/algogeeks?hl=en.
>

-- 
You received this message because you are subscribed to the Google Groups 
"Algorithm Geeks" group.
To post to this group, send email to algoge...@googlegroups.com.
To unsubscribe from this group, send email to 
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at 
http://groups.google.com/group/algogeeks?hl=en.

Re: [algogeeks] Re: find duplicate and missing element

[Raj Jagvanshi]

in ur algo i confuse in solving eqn

On Wed, Sep 1, 2010 at 6:31 PM, Dave  wrote:

> @Raj: Best what?
>
> Dave
>
> On Sep 1, 12:08 am, Raj Jagvanshi  wrote:
> > Thanks Dave
> > but i want best
> >
> >
> >
> > On Wed, Sep 1, 2010 at 7:14 AM, Dave  wrote:
> > > Suppose that x is duplicated and y is omitted. Then the sum of the
> > > numbers would be 5050 + x - y. Similarly, the sums of the squares of
> > > the numbers would be 338,350 + x^2 - y^2. Calculate the sum and sum of
> > > squares of the numbers and solve the resulting equations for x and y.
> >
> > > Dave
> >
> > > On Aug 31, 1:57 pm, Raj Jagvanshi  wrote:
> > > >   There is an array having distinct 100 elements from 1 to 100
> > > >  but by mistake some no is duplicated and a no is missed.
> > > >  Find the duplicate no and missing no.
> >
> > > > Thanks
> > > > Raj Jagvanshi
> >
> > > --
> > > You received this message because you are subscribed to the Google
> Groups
> > > "Algorithm Geeks" group.
> > > To post to this group, send email to algoge...@googlegroups.com.
> > > To unsubscribe from this group, send email to
> > > algogeeks+unsubscr...@googlegroups.com
> 
> > > .
> > > For more options, visit this group at
> > >http://groups.google.com/group/algogeeks?hl=en.- Hide quoted text -
> >
> > - Show quoted text -
>
> --
> You received this message because you are subscribed to the Google Groups
> "Algorithm Geeks" group.
> To post to this group, send email to algoge...@googlegroups.com.
> To unsubscribe from this group, send email to
> algogeeks+unsubscr...@googlegroups.com
> .
> For more options, visit this group at
> http://groups.google.com/group/algogeeks?hl=en.
>
>

-- 
You received this message because you are subscribed to the Google Groups 
"Algorithm Geeks" group.
To post to this group, send email to algoge...@googlegroups.com.
To unsubscribe from this group, send email to 
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at 
http://groups.google.com/group/algogeeks?hl=en.

Re: [algogeeks] Re: find duplicate and missing element

[dinesh bansal]

can you explain on your algorithm. Are you using any extra array.

On Wed, Sep 1, 2010 at 11:08 AM, Dhritiman Das wrote:

>
> Given a array, A[1..n], do the following.
> Start from i=1 and try placing each number in its correct position in the
> array.
> If the number is already in its correct position, go ahead. if (A[i] == i)
> , i++
> else if the number was already restored to its correct position, then it is
> a duplicate , so remember it and move ahead if (A[A[i]] == A[i]), dup =
> A[i], i++ ;
> else
>   swap the elements at the current index i and that at A[i]'s correct
> position in the array.
> continue this until all numbers are placed in their correct position in the
> array
> Finally, A[missing] will be dup.
> O(n)
>
>
>
> On Wed, Sep 1, 2010 at 7:14 AM, Dave  wrote:
>
>> Suppose that x is duplicated and y is omitted. Then the sum of the
>> numbers would be 5050 + x - y. Similarly, the sums of the squares of
>> the numbers would be 338,350 + x^2 - y^2. Calculate the sum and sum of
>> squares of the numbers and solve the resulting equations for x and y.
>>
>> Dave
>>
>> On Aug 31, 1:57 pm, Raj Jagvanshi  wrote:
>> >   There is an array having distinct 100 elements from 1 to 100
>> >  but by mistake some no is duplicated and a no is missed.
>> >  Find the duplicate no and missing no.
>> >
>> > Thanks
>> > Raj Jagvanshi
>>
>> --
>> You received this message because you are subscribed to the Google Groups
>> "Algorithm Geeks" group.
>> To post to this group, send email to algoge...@googlegroups.com.
>> To unsubscribe from this group, send email to
>> algogeeks+unsubscr...@googlegroups.com
>> .
>> For more options, visit this group at
>> http://groups.google.com/group/algogeeks?hl=en.
>>
>>
>  --
> You received this message because you are subscribed to the Google Groups
> "Algorithm Geeks" group.
> To post to this group, send email to algoge...@googlegroups.com.
> To unsubscribe from this group, send email to
> algogeeks+unsubscr...@googlegroups.com
> .
> For more options, visit this group at
> http://groups.google.com/group/algogeeks?hl=en.
>



-- 
Dinesh Bansal
The Law of Win says, "Let's not do it your way or my way; let's do it the
best way."

-- 
You received this message because you are subscribed to the Google Groups 
"Algorithm Geeks" group.
To post to this group, send email to algoge...@googlegroups.com.
To unsubscribe from this group, send email to 
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at 
http://groups.google.com/group/algogeeks?hl=en.

[algogeeks] Re: find duplicate and missing element

[Dave]

@Raj: Best what?

Dave

On Sep 1, 12:08 am, Raj Jagvanshi  wrote:
> Thanks Dave
> but i want best
>
>
>
> On Wed, Sep 1, 2010 at 7:14 AM, Dave  wrote:
> > Suppose that x is duplicated and y is omitted. Then the sum of the
> > numbers would be 5050 + x - y. Similarly, the sums of the squares of
> > the numbers would be 338,350 + x^2 - y^2. Calculate the sum and sum of
> > squares of the numbers and solve the resulting equations for x and y.
>
> > Dave
>
> > On Aug 31, 1:57 pm, Raj Jagvanshi  wrote:
> > >   There is an array having distinct 100 elements from 1 to 100
> > >  but by mistake some no is duplicated and a no is missed.
> > >  Find the duplicate no and missing no.
>
> > > Thanks
> > > Raj Jagvanshi
>
> > --
> > You received this message because you are subscribed to the Google Groups
> > "Algorithm Geeks" group.
> > To post to this group, send email to algoge...@googlegroups.com.
> > To unsubscribe from this group, send email to
> > algogeeks+unsubscr...@googlegroups.com
> > .
> > For more options, visit this group at
> >http://groups.google.com/group/algogeeks?hl=en.- Hide quoted text -
>
> - Show quoted text -

-- 
You received this message because you are subscribed to the Google Groups 
"Algorithm Geeks" group.
To post to this group, send email to algoge...@googlegroups.com.
To unsubscribe from this group, send email to 
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at 
http://groups.google.com/group/algogeeks?hl=en.

Re: [algogeeks] Re: find duplicate and missing element

[Raj Jagvanshi]

Thanks Dave
but i want best

On Wed, Sep 1, 2010 at 7:14 AM, Dave  wrote:

> Suppose that x is duplicated and y is omitted. Then the sum of the
> numbers would be 5050 + x - y. Similarly, the sums of the squares of
> the numbers would be 338,350 + x^2 - y^2. Calculate the sum and sum of
> squares of the numbers and solve the resulting equations for x and y.
>
> Dave
>
> On Aug 31, 1:57 pm, Raj Jagvanshi  wrote:
> >   There is an array having distinct 100 elements from 1 to 100
> >  but by mistake some no is duplicated and a no is missed.
> >  Find the duplicate no and missing no.
> >
> > Thanks
> > Raj Jagvanshi
>
> --
> You received this message because you are subscribed to the Google Groups
> "Algorithm Geeks" group.
> To post to this group, send email to algoge...@googlegroups.com.
> To unsubscribe from this group, send email to
> algogeeks+unsubscr...@googlegroups.com
> .
> For more options, visit this group at
> http://groups.google.com/group/algogeeks?hl=en.
>
>

-- 
You received this message because you are subscribed to the Google Groups 
"Algorithm Geeks" group.
To post to this group, send email to algoge...@googlegroups.com.
To unsubscribe from this group, send email to 
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at 
http://groups.google.com/group/algogeeks?hl=en.

Re: [algogeeks] Re: find duplicate and missing element

[Dhritiman Das]

Given a array, A[1..n], do the following.
Start from i=1 and try placing each number in its correct position in the
array.
If the number is already in its correct position, go ahead. if (A[i] == i) ,
i++
else if the number was already restored to its correct position, then it is
a duplicate , so remember it and move ahead if (A[A[i]] == A[i]), dup =
A[i], i++ ;
else
  swap the elements at the current index i and that at A[i]'s correct
position in the array.
continue this until all numbers are placed in their correct position in the
array
Finally, A[missing] will be dup.
O(n)


On Wed, Sep 1, 2010 at 7:14 AM, Dave  wrote:

> Suppose that x is duplicated and y is omitted. Then the sum of the
> numbers would be 5050 + x - y. Similarly, the sums of the squares of
> the numbers would be 338,350 + x^2 - y^2. Calculate the sum and sum of
> squares of the numbers and solve the resulting equations for x and y.
>
> Dave
>
> On Aug 31, 1:57 pm, Raj Jagvanshi  wrote:
> >   There is an array having distinct 100 elements from 1 to 100
> >  but by mistake some no is duplicated and a no is missed.
> >  Find the duplicate no and missing no.
> >
> > Thanks
> > Raj Jagvanshi
>
> --
> You received this message because you are subscribed to the Google Groups
> "Algorithm Geeks" group.
> To post to this group, send email to algoge...@googlegroups.com.
> To unsubscribe from this group, send email to
> algogeeks+unsubscr...@googlegroups.com
> .
> For more options, visit this group at
> http://groups.google.com/group/algogeeks?hl=en.
>
>

-- 
You received this message because you are subscribed to the Google Groups 
"Algorithm Geeks" group.
To post to this group, send email to algoge...@googlegroups.com.
To unsubscribe from this group, send email to 
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at 
http://groups.google.com/group/algogeeks?hl=en.

[algogeeks] Re: find duplicate and missing element

[Dave]

Suppose that x is duplicated and y is omitted. Then the sum of the
numbers would be 5050 + x - y. Similarly, the sums of the squares of
the numbers would be 338,350 + x^2 - y^2. Calculate the sum and sum of
squares of the numbers and solve the resulting equations for x and y.

Dave

On Aug 31, 1:57 pm, Raj Jagvanshi  wrote:
>   There is an array having distinct 100 elements from 1 to 100
>  but by mistake some no is duplicated and a no is missed.
>  Find the duplicate no and missing no.
>
> Thanks
> Raj Jagvanshi

-- 
You received this message because you are subscribed to the Google Groups 
"Algorithm Geeks" group.
To post to this group, send email to algoge...@googlegroups.com.
To unsubscribe from this group, send email to 
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at 
http://groups.google.com/group/algogeeks?hl=en.