[algogeeks] Re: find duplicate and missing element

2010-09-03 Thread 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: Simple reVerse

2010-09-03 Thread albert theboss
if input is 12345
then the output should be 54321

-- 
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: Simple reVerse

2010-09-03 Thread albert theboss
@Dave but i tried the code its not working 

  Its giving 1 for all the input

  could u explain the code please 

-- 
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: Simple reVerse

2010-09-03 Thread Dave
I presume that you mean reversing the order of the bits, so that the
low-order bit goes to the high-order position and vice-versa. Assuming
32 bit integers, this does the trick:

int r;
r = ( ( x && 0x ) >> 16 ) || ( ( x && 0x ) <<
16 );
r = ( ( r && 0xff00ff00 ) >>  8 ) || ( ( r && 0x00ff00ff ) <<
8 );
r = ( ( r && 0xf0f0f0f0 ) >>  4 ) || ( ( r && 0x0f0f0f0f ) <<
4 );
r = ( ( r && 0x ) >>  2 ) || ( ( r && 0x ) <<
2 );
r = ( ( r && 0x ) >>  1 ) || ( ( r && 0x ) <<
1 );
return r;

Dave

On Sep 3, 1:00 pm, Albert  wrote:
> int reverse(int x)
> {
>
> ...
> ...
> 
>
> }
>
> complete the above code such that it returns the reverse of 'x' 
>
> condition here is u should not use loops and global as well as static
> variable..
>
> try to give all the possible solutions for this  ...

-- 
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: Amazon interview Question (Array yet again!)

2010-09-03 Thread Discover
nice explanation gene :)

On Sep 2, 8:35 am, Gene  wrote:
> Okay.  First, you can make the DP more efficient than the one I gave
> earlier. You don't need to scan the whole previous column when
> calculating costs of decrementing.  Rather there are only two
> possibilities.
>
> I will add that rahul patil's solution looks correct, but it's
> exponential time.  DP is better for this problem.
>
> Remember C(n, m) is the cost of making a[1 .. n] into a non-decreasing
> sequence with the last element being no more than m.  And we always
> draw m from the set V of values in a.
>
> So here is the new DP:
>
> C(1, m) = max(a[1] - m, 0)  // first row only decrement is possible
> C(n, m) = min (
>   a[n] + C(n - 1, m),   // delete
>   (a[n] <= m) ?  C(n - 1, a[n]) : C(n - 1, m) + a[n] - m // decrement
> )
>
> In case you don't follow, the "//delete" line is saying that we
> already know the cost of making everything up to element n-1 non-
> decreasing and no more than m.  This, by recursive assumption, is just
> C(n-1,m).  The additional cost of deleting a[n] is a[n].
>
> The "//decrement" line is similar, but there are 2 cases.  If a[n] is
> more than m, we must decrement it.  The cost here consists of making
> everything up to n-1 non-decreasing and no more than m, i.e. C(n-1,m).
> Plus we have the cost of chopping a[n] down to m, which is a[n]-m.
>
> In the other case, a[n] is m or less.  So there's no need to
> decrement, but we must get the elements a[1..n-1] to be no more than
> a[n].  Again by recursive assumption this cost is C(n-1,a[n]).
>
> Here is an example.  Suppose we have a = [5, 1, 1, 1, 3, 1].  The
> least cost here is obtained by decrementing the 5 to 1 (cost 4) and
> deleting the final 1 (cost 1) for a total cost of 5.
>
> So let's try the algorithm. (You must view this with a fixed font.)
>
> Table of C(n, m) values:
>     m = 1   3   5
> n = 1 : 4   2   0
> n = 2 : 4   3*  1*
> n = 3 : 4   4   2*
> n = 4 : 4   4   3*
> n = 5 : 6m  4   4
> n = 6 : 6   5*  5*
>
> Here * means C resulted from decrementing and "m" means that a
> decrement was based on the value of m rather than a[n].
>
> We take the answer from C(6,5) = 5.
>
> Implementing this is a little tricky because m values are drawn from
> V.  You could use a hash table for the m-axis.  But it's more
> efficient to store V in an array and convert all the values of m in
> the DP into indices of V.  Because all the indices lie in [ 1 .. |
> V| ], we can use simple arrays rather than hash tables to represent
> the rows of the table C.
>
> We only need 2 rows at a time, so O(|V|) storage does the job.
>
> For C, we also need to convert all the indices to origin 0.
>
> So here's the final O(n^2) code.  I think this is a correct
> implementation.  If anyone has an example that breaks it, I'd like to
> see.
>
> #include 
>
> #define NMAX 1
>
> int cost(int *a, int N)
> {
>   int i, j, max, Nv;
>   int V[NMAX], A[NMAX], B[NMAX];
>   int *Cm = A, *Cn = B;  // (n-1)'th and n'th rows of C
>
>   // Compute set V with no duplicates.
>   // Remember where max element is.
>   Nv = max = 0;
>   for (i = 0; i < N; i++) {
>     for (j = 0; j < Nv; j++)
>       if (a[i] == V[j])
>         break;
>     if (j == Nv) {
>       V[Nv++] = a[i];
>       if (V[j] > V[max])
>         max = j;
>     }
>     a[i] = j; // Convert a to indices.
>   }
>   // Fill in first row of C.
>   for (i = 0; i < Nv; i++)
>     Cm[i] = (V[a[0]] >= V[i]) ? V[a[0]] - V[i] : 0;
>
>   // Fill in the rest of the rows of C.
>   for (i = 1; i < N; i++) {
>     for (j = 0; j < Nv; j++) {
>       int del = Cm[j] + V[a[i]];
>       int dec = (V[a[i]] <= V[j]) ? Cm[a[i]] : Cm[j] + V[a[i]] - V[j];
>       Cn[j] = (del < dec) ? del : dec;
>     }
>     // Swap row buffers so current becomes previous.
>     int *tmp = Cn;  Cn = Cm; Cm = tmp;
>   }
>   return Cm[max];
>
> }
>
> int main(void)
> {
>   static int a[] = { 5, 1, 1, 1, 3, 1 };
>   printf("Min cost = %d\n", cost(a, sizeof a / sizeof a[0]));
>   return 0;
>
> }
>
> On Aug 30, 9:19 pm, vikash jain  wrote:
>
>
>
> > @gene ..if u just give an example herethat  will make things more
> > clear...

-- 
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: Amazon interview Question (Array yet again!)

2010-09-03 Thread Discover
@gene: nice solution..

but it's not working for a[]={20,22,13,11};

ur code will give soln : 24
but ans should be: 22 {11,11,11,11}

pls correct me if i m wrong


On Aug 28, 8:26 am, jagadish  wrote:
> @Gene: Thanks alot! :-) your solution works like charm!
>
> On Aug 28, 7:09 am, Gene  wrote:
>
>
>
> > This is a nice problem.  It looks like a trivial matroid, so a greedy
> > algorithm will work fine.  The obvious greedy algorithm is to work
> > left-to-right and incorporate elements into the sorted order one-by-
> > one.  In each case, you have 2 choices.  The first is to decrement
> > elements to the left by the amount needed to restore non-decreasing
> > order.  The second is to delete the new element.  The cost of each is
> > easy to calculate.  Pick the choice with least cost and continue.
> > This algorithm is O(n^2).  There may be a faster way to do it, but I
> > can't see one.
>
> > #include 
>
> > int make_nondecreasing(int *a, int n)
> > {
> >   int i, j, dec, dec_cost, total_cost;
>
> >   total_cost = 0;
> >   for (i = 0; i < n - 1; i++) {
>
> >     // If we find a decrease...
> >     if (a[i] > a[i + 1]) {
>
> >       // Find cost of decrementing all to the left.
> >       dec_cost = dec = a[i] - a[i + 1];
> >       for (j = i - 1; j >= 0; j--) {
>
> >         // Find decrement that would be needed.
> >         dec += a[j] - a[j + 1];
>
> >         // If no decement, we're done.
> >         if (dec <= 0)
> >           break;
>
> >         // Count cost of decrement.
> >         dec_cost += dec;
> >       }
>
> >       // Compare decrement cost with deletion cost.
> >       if (dec_cost < a[i + 1]) {
>
> >         // Decrement is cheaper.  Do it.
> >         for (j = i; j >= 0; j--) {
> >           if (a[j] > a[i + 1])
> >             a[j] = a[i + 1];
> >         }
> >         total_cost += dec_cost;
> >       }
> >       else {
>
> >         // Deletion is cheaper.  Do it.
> >         total_cost += a[i + 1];
> >         for (j = i + 1; j < n - 1; j++)
> >           a[j] = a[j + 1];
> >         --n;
> >       }
> >     }
> >   }
> >   return total_cost;
>
> > }
>
> > int main(void)
> > {
> >   int a[] = { 14, 15, 16, 13, 11, 18 };
> >   //int a[] = { 4, 3, 5, 6};
> >   //int a[] = { 10, 3, 11, 12 };
> >   int cost = make_nondecreasing(a, sizeof a / sizeof a[0]);
> >   printf("cost=%d\n", cost);
> >   return 0;
>
> > }
>
> > On Aug 27, 12:15 pm, jagadish  wrote:
>
> > > You are given an array of positive integers. Convert it to a sorted
> > > array with minimum cost. Only valid operation are
> > > 1) Decrement -> cost = 1
> > > 2) Delete an element completely from the array -> cost = value of
> > > element
>
> > > For example:
> > > 4,3,5,6, -> cost 1
> > > 10,3,11,12 -> cost 3

-- 
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] Simple reVerse

2010-09-03 Thread Albert
int reverse(int x)
{

...
...


}

complete the above code such that it returns the reverse of 'x' 

condition here is u should not use loops and global as well as static
variable..

try to give all the possible solutions for this  ...

-- 
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: Take 5 digit number and find 2 power that number.............

2010-09-03 Thread Discover
But how the number(in decimal form) will be displayedif ques
demands so.

On Sep 2, 1:49 pm, saurabh singh  wrote:
> Suppose the number of shifts be x.
> Also let the integer be represented by 16 bits on that machine.
> Now take int n= (int)(x/16 + 0.5), to take the upper cap on result :) .
> SO having 2^x will be same as doing 2<<(x-1) so essentially if we represent
> the resultant number in a linked list of nodes, where each node can store an
> integer, then the bit position at 2+x-1=x+1 will be set as 1 and this
> (x+1)th nit will fall in (x+1)/16th node in linked list also in that node
> (x+1)%16 will give the position of bit to be set.
>
> On Thu, Sep 2, 2010 at 1:32 PM, ashish agarwal 
>
>
>
>
> > wrote:
> > I think it will be 1<
> > On Wed, Sep 1, 2010 at 10:53 PM, Yan Wang wrote:
>
> >> Maybe you misunderstand the question.
> >> The question is how to compute 2^X where 0 <= X <= 9?
> >> How?
>
> >> On Wed, Sep 1, 2010 at 10:48 PM, Ruturaj  wrote:
> >> > a 5 digit number is of order 10^5 which is << 10^16 of which int in C
> >> > is of size.
> >> > Just multiply both numbers.
>
> >> > On Sep 2, 10:39 am, prasad rao  wrote:
> >> >> Program that takes a 5 digit number and calculates 2 power that number
> >> and
> >> >> prints it and should not use the Big-integer and Exponential
> >> Function's.
>
> >> > --
> >> > 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 >>  .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 >>  .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 > .com>
> > .
> > For more options, visit this group at
> >http://groups.google.com/group/algogeeks?hl=en.
>
> --
> Thanks & Regards,
> Saurabh

-- 
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: Amazon intern Question

2010-09-03 Thread Dhruvesh !!
Trie-traverse search will be best..

On Thu, Sep 2, 2010 at 8:10 PM, Manjunath Manohar
wrote:

> trie will be the best choice for this..
>
> --
> 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.
>



-- 
Dhruvesh Kumar
Mobile No.: +919911314113
M.C.A.,
Department of Computer Science,
Delhi University, INDIA

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

2010-09-03 Thread 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

2010-09-03 Thread 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