[algogeeks] Re: Missing numbers
Consider the below e.g
n+2 array is {1,2,3,4}
and given the n array as {3,4} then can you pls explain how ur logic
finds 1,2 as missing?
thanks
On Aug 4, 9:35 am, Prunthaban Kanthakumar pruntha...@gmail.com
wrote:
Here is the right answer:
Find the sum of missing numbers. Call it S (this is a easy to do).
Now the two missing numbers are such that one is =S/2 and the other is
S/2
Have two variables S1 and S2, traverse the array and add everything = S/2
to S1 and S/2 to S2.
Now
First number = (Sum of numbers from 1 to S/2) - S1
Second Number = (Sum of numbers from [S/2 + 1] to n+2) - S2
O(n) time and O(1) space.
On Tue, Aug 4, 2009 at 3:28 AM, Karthik Singaram Lakshmanan
karthiksinga...@gmail.com wrote:
well..will this work?
x + y = SUM(1:N+2) - SUM(array) = a
x^2 + y^2 = SUM(1^2:(N+2)^2) - SUM(array.^2) = b
so (a^2 - b) = 2xy
so xy = (a^2-b)/2 = k (say)
now,
x + (k/x) = a
x^2 + k = ax
(x, y) = (a +/- sqrt(a^2-4k))/2
I may not have written the equations correctly (need coffee !!!)
but you get the general idea...
solve a quadratic equation to solve for (x+y) = a and (x^2 + y^2) = b
- Karthik
--~--~-~--~~~---~--~~
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algogeeks@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
-~--~~~~--~~--~--~---
[algogeeks] Re: Missing numbers
Elegant.. I think it can't be better than this. Identifying that each of them are on different sides of S/2 was the key! On Tue, Aug 4, 2009 at 10:05 AM, Prunthaban Kanthakumar pruntha...@gmail.com wrote: Here is the right answer: Find the sum of missing numbers. Call it S (this is a easy to do). Now the two missing numbers are such that one is =S/2 and the other is S/2 Have two variables S1 and S2, traverse the array and add everything = S/2 to S1 and S/2 to S2. Now First number = (Sum of numbers from 1 to S/2) - S1 Second Number = (Sum of numbers from [S/2 + 1] to n+2) - S2 O(n) time and O(1) space. On Tue, Aug 4, 2009 at 3:28 AM, Karthik Singaram Lakshmanan karthiksinga...@gmail.com wrote: well..will this work? x + y = SUM(1:N+2) - SUM(array) = a x^2 + y^2 = SUM(1^2:(N+2)^2) - SUM(array.^2) = b so (a^2 - b) = 2xy so xy = (a^2-b)/2 = k (say) now, x + (k/x) = a x^2 + k = ax (x, y) = (a +/- sqrt(a^2-4k))/2 I may not have written the equations correctly (need coffee !!!) but you get the general idea... solve a quadratic equation to solve for (x+y) = a and (x^2 + y^2) = b - Karthik --~--~-~--~~~---~--~~ You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@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 -~--~~~~--~~--~--~---
[algogeeks] Re: Missing numbers
Pretty! :) Channa Bankapur wrote: Elegant.. I think it can't be better than this. Identifying that each of them are on different sides of S/2 was the key! On Tue, Aug 4, 2009 at 10:05 AM, Prunthaban Kanthakumar pruntha...@gmail.com mailto:pruntha...@gmail.com wrote: Here is the right answer: Find the sum of missing numbers. Call it S (this is a easy to do). Now the two missing numbers are such that one is =S/2 and the other is S/2 Have two variables S1 and S2, traverse the array and add everything = S/2 to S1 and S/2 to S2. Now First number = (Sum of numbers from 1 to S/2) - S1 Second Number = (Sum of numbers from [S/2 + 1] to n+2) - S2 O(n) time and O(1) space. On Tue, Aug 4, 2009 at 3:28 AM, Karthik Singaram Lakshmanan karthiksinga...@gmail.com mailto:karthiksinga...@gmail.com wrote: well..will this work? x + y = SUM(1:N+2) - SUM(array) = a x^2 + y^2 = SUM(1^2:(N+2)^2) - SUM(array.^2) = b so (a^2 - b) = 2xy so xy = (a^2-b)/2 = k (say) now, x + (k/x) = a x^2 + k = ax (x, y) = (a +/- sqrt(a^2-4k))/2 I may not have written the equations correctly (need coffee !!!) but you get the general idea... solve a quadratic equation to solve for (x+y) = a and (x^2 + y^2) = b - Karthik --~--~-~--~~~---~--~~ You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@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 -~--~~~~--~~--~--~--- begin:vcard fn:Anil C R n:C R;Anil email;internet:cr.a...@gmail.com version:2.1 end:vcard
[algogeeks] Re: Missing numbers
after getting one number cant u subtract from S?? On Tue, Aug 4, 2009 at 5:53 PM, Anil C R cr.a...@gmail.com wrote: Pretty! :) Channa Bankapur wrote: Elegant.. I think it can't be better than this. Identifying that each of them are on different sides of S/2 was the key! On Tue, Aug 4, 2009 at 10:05 AM, Prunthaban Kanthakumar pruntha...@gmail.com mailto:pruntha...@gmail.com wrote: Here is the right answer: Find the sum of missing numbers. Call it S (this is a easy to do). Now the two missing numbers are such that one is =S/2 and the other is S/2 Have two variables S1 and S2, traverse the array and add everything = S/2 to S1 and S/2 to S2. Now First number = (Sum of numbers from 1 to S/2) - S1 Second Number = (Sum of numbers from [S/2 + 1] to n+2) - S2 O(n) time and O(1) space. On Tue, Aug 4, 2009 at 3:28 AM, Karthik Singaram Lakshmanan karthiksinga...@gmail.com mailto:karthiksinga...@gmail.com wrote: well..will this work? x + y = SUM(1:N+2) - SUM(array) = a x^2 + y^2 = SUM(1^2:(N+2)^2) - SUM(array.^2) = b so (a^2 - b) = 2xy so xy = (a^2-b)/2 = k (say) now, x + (k/x) = a x^2 + k = ax (x, y) = (a +/- sqrt(a^2-4k))/2 I may not have written the equations correctly (need coffee !!!) but you get the general idea... solve a quadratic equation to solve for (x+y) = a and (x^2 + y^2) = b - Karthik --~--~-~--~~~---~--~~ You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@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 -~--~~~~--~~--~--~---
[algogeeks] Re: Missing numbers
after getting one number cant u subtract from S?? On Tue, Aug 4, 2009 at 5:53 PM, Anil C R cr.a...@gmail.com wrote: Pretty! :) Channa Bankapur wrote: Elegant.. I think it can't be better than this. Identifying that each of them are on different sides of S/2 was the key! On Tue, Aug 4, 2009 at 10:05 AM, Prunthaban Kanthakumar pruntha...@gmail.com mailto:pruntha...@gmail.com wrote: Here is the right answer: Find the sum of missing numbers. Call it S (this is a easy to do). Now the two missing numbers are such that one is =S/2 and the other is S/2 Have two variables S1 and S2, traverse the array and add everything = S/2 to S1 and S/2 to S2. Now First number = (Sum of numbers from 1 to S/2) - S1 Second Number = (Sum of numbers from [S/2 + 1] to n+2) - S2 O(n) time and O(1) space. On Tue, Aug 4, 2009 at 3:28 AM, Karthik Singaram Lakshmanan karthiksinga...@gmail.com mailto:karthiksinga...@gmail.com wrote: well..will this work? x + y = SUM(1:N+2) - SUM(array) = a x^2 + y^2 = SUM(1^2:(N+2)^2) - SUM(array.^2) = b so (a^2 - b) = 2xy so xy = (a^2-b)/2 = k (say) now, x + (k/x) = a x^2 + k = ax (x, y) = (a +/- sqrt(a^2-4k))/2 I may not have written the equations correctly (need coffee !!!) but you get the general idea... solve a quadratic equation to solve for (x+y) = a and (x^2 + y^2) = b - Karthik --~--~-~--~~~---~--~~ You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@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 -~--~~~~--~~--~--~---
[algogeeks] Re: Missing numbers
wont it be additional overhead to sum again from S/2+1 to n+2.instead subtract from s the number we got ??? On Tue, Aug 4, 2009 at 9:21 PM, sharad kumar aryansmit3...@gmail.comwrote: after getting one number cant u subtract from S?? On Tue, Aug 4, 2009 at 5:53 PM, Anil C R cr.a...@gmail.com wrote: Pretty! :) Channa Bankapur wrote: Elegant.. I think it can't be better than this. Identifying that each of them are on different sides of S/2 was the key! On Tue, Aug 4, 2009 at 10:05 AM, Prunthaban Kanthakumar pruntha...@gmail.com mailto:pruntha...@gmail.com wrote: Here is the right answer: Find the sum of missing numbers. Call it S (this is a easy to do). Now the two missing numbers are such that one is =S/2 and the other is S/2 Have two variables S1 and S2, traverse the array and add everything = S/2 to S1 and S/2 to S2. Now First number = (Sum of numbers from 1 to S/2) - S1 Second Number = (Sum of numbers from [S/2 + 1] to n+2) - S2 O(n) time and O(1) space. On Tue, Aug 4, 2009 at 3:28 AM, Karthik Singaram Lakshmanan karthiksinga...@gmail.com mailto:karthiksinga...@gmail.com wrote: well..will this work? x + y = SUM(1:N+2) - SUM(array) = a x^2 + y^2 = SUM(1^2:(N+2)^2) - SUM(array.^2) = b so (a^2 - b) = 2xy so xy = (a^2-b)/2 = k (say) now, x + (k/x) = a x^2 + k = ax (x, y) = (a +/- sqrt(a^2-4k))/2 I may not have written the equations correctly (need coffee !!!) but you get the general idea... solve a quadratic equation to solve for (x+y) = a and (x^2 + y^2) = b - Karthik --~--~-~--~~~---~--~~ You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@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 -~--~~~~--~~--~--~---
[algogeeks] Re: Missing numbers
well..will this work? x + y = SUM(1:N+2) - SUM(array) = a x^2 + y^2 = SUM(1^2:(N+2)^2) - SUM(array.^2) = b so (a^2 - b) = 2xy so xy = (a^2-b)/2 = k (say) now, x + (k/x) = a x^2 + k = ax (x, y) = (a +/- sqrt(a^2-4k))/2 I may not have written the equations correctly (need coffee !!!) but you get the general idea... solve a quadratic equation to solve for (x+y) = a and (x^2 + y^2) = b - Karthik --~--~-~--~~~---~--~~ You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@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 -~--~~~~--~~--~--~---
[algogeeks] Re: Missing numbers
Here is the right answer: Find the sum of missing numbers. Call it S (this is a easy to do). Now the two missing numbers are such that one is =S/2 and the other is S/2 Have two variables S1 and S2, traverse the array and add everything = S/2 to S1 and S/2 to S2. Now First number = (Sum of numbers from 1 to S/2) - S1 Second Number = (Sum of numbers from [S/2 + 1] to n+2) - S2 O(n) time and O(1) space. On Tue, Aug 4, 2009 at 3:28 AM, Karthik Singaram Lakshmanan karthiksinga...@gmail.com wrote: well..will this work? x + y = SUM(1:N+2) - SUM(array) = a x^2 + y^2 = SUM(1^2:(N+2)^2) - SUM(array.^2) = b so (a^2 - b) = 2xy so xy = (a^2-b)/2 = k (say) now, x + (k/x) = a x^2 + k = ax (x, y) = (a +/- sqrt(a^2-4k))/2 I may not have written the equations correctly (need coffee !!!) but you get the general idea... solve a quadratic equation to solve for (x+y) = a and (x^2 + y^2) = b - Karthik --~--~-~--~~~---~--~~ You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@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 -~--~~~~--~~--~--~---
[algogeeks] Re: Missing numbers
@sharad.. ok then wat i m making a point u dont try 2 understand.. take n= billions let u have ds to handle 1 billion number then wat about n! .. how will u handle it . ??? try 2 understand otherwise u go for soln. but for placement purpose this soln is wrong. email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com For more options, visit this group at http://groups.google.com/group/algogeeks -~--~~~~--~~--~--~--- --~--~-~--~~~---~--~~ You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@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 -~--~~~~--~~--~--~---
[algogeeks] Re: Missing numbers
@Vivek I had told abt tat border case already once.. Suppose the two missin numbers are greater than n, then m==0 when exitin the loop. So they will be n+1 and n+2 only. in case, one of the missin numbers is greater than n, then m==1, and can be simply found by subtracting the (array_sum+x[0] ) from (sumof 1 to n+2) numbers. Hope it works.. --~--~-~--~~~---~--~~ You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@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 -~--~~~~--~~--~--~---
[algogeeks] Re: Missing numbers
@all suming the 1 to n+2 or n will not solve this problem.. it may give overflow problem.. this is not the soln... --~--~-~--~~~---~--~~ You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@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 -~--~~~~--~~--~--~---
[algogeeks] Re: Missing numbers
we have got additional data typees to handle sir,like biginteger in java.string in c++ etc.its a linear programming problem sir. On Sat, Aug 1, 2009 at 6:12 PM, ankur aggarwal ankur.mast@gmail.comwrote: @all suming the 1 to n+2 or n will not solve this problem.. it may give overflow problem.. this is not the soln... --~--~-~--~~~---~--~~ You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@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 -~--~~~~--~~--~--~---
[algogeeks] Re: Missing numbers
@sharad then wat about memory wastage?? memory shud be taken care of.. On Sat, Aug 1, 2009 at 7:39 PM, sharad kumar aryansmit3...@gmail.comwrote: we have got additional data typees to handle sir,like biginteger in java.string in c++ etc.its a linear programming problem sir. On Sat, Aug 1, 2009 at 6:12 PM, ankur aggarwal ankur.mast@gmail.comwrote: @all suming the 1 to n+2 or n will not solve this problem.. it may give overflow problem.. this is not the soln... --~--~-~--~~~---~--~~ You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@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 -~--~~~~--~~--~--~---
[algogeeks] Re: Missing numbers
yes sir,bigint can handle till 100! or more .incase of overflow we can make use of string On Sat, Aug 1, 2009 at 8:00 PM, ankur aggarwal ankur.mast@gmail.comwrote: @sharad then wat about memory wastage?? memory shud be taken care of.. On Sat, Aug 1, 2009 at 7:39 PM, sharad kumar aryansmit3...@gmail.comwrote: we have got additional data typees to handle sir,like biginteger in java.string in c++ etc.its a linear programming problem sir. On Sat, Aug 1, 2009 at 6:12 PM, ankur aggarwal ankur.mast@gmail.comwrote: @all suming the 1 to n+2 or n will not solve this problem.. it may give overflow problem.. this is not the soln... --~--~-~--~~~---~--~~ You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@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 -~--~~~~--~~--~--~---
[algogeeks] Re: Missing numbers
Try {2, 1}
On Sat, Aug 1, 2009 at 11:45 AM, Devi G devs...@gmail.com wrote:
@Vivek
I had told abt tat border case already once..
Suppose the two missin numbers are greater than n, then m==0 when exitin
the loop.
So they will be n+1 and n+2 only.
in case, one of the missin numbers is greater than n, then m==1, and can be
simply found by subtracting the (array_sum+x[0] ) from (sumof 1 to n+2)
numbers.
Hope it works..
--~--~-~--~~~---~--~~
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algogeeks@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
-~--~~~~--~~--~--~---
[algogeeks] Re: Missing numbers
There is something wrong with it. I tried your code like this.
int i, n = 8, a[9] = {-1,3,5,1,2,9,10,8,6}; //a[0] is never touched in the
logic
for(i=1; i=n ;i++ ) //for ease of understanding starting the
array with 1.
{
if(a[ i ] n )
continue;
else
a[ a [ i ] ]*=n;
}
int x[2], m = 0;
for ( int i = 1; i =n ; i++)
{
if(a[ i ] % n == 0)
continue;
else
{
x[m++ ] = i;
if(m == 2) break;
}
}
After first for loop, the array a has
-1, 3, 40, 8, 2, 72, 10, 8, 384
And finally, answer array x has 1 and 4, which is not correct.
Could you elaborate your logic in pseudocode?
Thanks,
Channa
On Thu, Jul 30, 2009 at 11:06 PM, Devi G devs...@gmail.com wrote:
I'm sorry.. misunderstood the problem and tot the missin numbers are to
be less than n.
Yet it can be modified to suit the pbm.
Suppose the two missin numbers are greater than n, then m==0 when exitin
the loop.
So they will be n+1 and n+2 only.
in case, one of the missin numbers is greater than n, then m==1, and can be
simply found by subtracting the (array_sum+x[0] ) from (sumof 1 to n+2)
numbers.
On Thu, Jul 30, 2009 at 10:55 PM, Devi G devs...@gmail.com wrote:
for(i=1; i=n ;i++ ) //for ease of understanding starting the
array with 1.
{
if(a[ i ] n )
continue;
else
a[ a [ i ] ]*=n;
}
int x[2], m = 0;
for ( int i = 1; i =n ; i++)
{
if(a[ i ] % n == 0)
continue;
else
{
x[m++ ] = i;
if(m == 2) break;
}
}
x[] now contain the two missing numbers in ascending order.
--~--~-~--~~~---~--~~
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algogeeks@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
-~--~~~~--~~--~--~---
[algogeeks] Re: Missing numbers
The logic is actually simple. Tot if we mark in some way an element when it's scanned, we can find the missing numbers in the second scannin. 3,5,1,2,9,10,8,6 When for loop sees '3' it knows elt 3 is there. So multiplies the number at 3rd position by some arbitrary number. (* I've taken the arbitrary number to be n here but CORRECT ONE IS n+3 cos n will fail in some cases*) so, when it sees '5' multiplies the number at 5th position by n+3. It skips when the numbr is greater than n. n+3 = 11 here. So,after first loop, 33, 55, 11, 2 , 99, 110, 8, 66. So now, in the second scan, the indices of all elts that are divisible by n+3 are present in the array. elts at 4th and 7th positions are not divisible. hence missing numbers are 4 and 7. --~--~-~--~~~---~--~~ You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@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 -~--~~~~--~~--~--~---
[algogeeks] Re: Missing numbers
check this out Let x and y be the missing number, Now equation 1 is : x + y = [n(n+1)/2] - S equation 2 is: x * y = N! /P solve both we get elements On Fri, Jul 31, 2009 at 8:27 PM, Devi G devs...@gmail.com wrote: The logic is actually simple. Tot if we mark in some way an element when it's scanned, we can find the missing numbers in the second scannin. 3,5,1,2,9,10,8,6 When for loop sees '3' it knows elt 3 is there. So multiplies the number at 3rd position by some arbitrary number. (* I've taken the arbitrary number to be n here but CORRECT ONE IS n+3 cos n will fail in some cases*) so, when it sees '5' multiplies the number at 5th position by n+3. It skips when the numbr is greater than n. n+3 = 11 here. So,after first loop, 33, 55, 11, 2 , 99, 110, 8, 66. So now, in the second scan, the indices of all elts that are divisible by n+3 are present in the array. elts at 4th and 7th positions are not divisible. hence missing numbers are 4 and 7. --~--~-~--~~~---~--~~ You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@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 -~--~~~~--~~--~--~---
[algogeeks] Re: Missing numbers
@Devi;
Consider this,
N = 2
The array elements should these (N+2), numbers : {1, 2, 3, 4}
If the given array is {4, 3}
Will your code work correctly?
2009/7/31 Devi G devs...@gmail.com
The logic is actually simple. Tot if we mark in some way an element when
it's scanned, we can find the missing numbers in the second scannin.
3,5,1,2,9,10,8,6
When for loop sees '3' it knows elt 3 is there. So multiplies the number at
3rd position by some arbitrary number. (* I've taken the arbitrary number
to be n here but CORRECT ONE IS n+3 cos n will fail in some cases*)
so, when it sees '5' multiplies the number at 5th position by n+3.
It skips when the numbr is greater than n.
n+3 = 11 here.
So,after first loop,
33, 55, 11, 2 , 99, 110, 8, 66.
So now, in the second scan, the indices of all elts that are divisible by
n+3 are present in the array.
elts at 4th and 7th positions are not divisible. hence missing numbers are
4 and 7.
--
Reduce, Reuse and Recycle
Regards,
Vivek.S
--~--~-~--~~~---~--~~
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algogeeks@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
-~--~~~~--~~--~--~---
[algogeeks] Re: Missing numbers
N! overflows... Try to write a program to find the value of 30! You don't have a variable that is large enough to store such a big number... 2009/7/31 sharad kumar aryansmit3...@gmail.com check this out Let x and y be the missing number, Now equation 1 is : x + y = [n(n+1)/2] - S equation 2 is: x * y = N! /P solve both we get elements On Fri, Jul 31, 2009 at 8:27 PM, Devi G devs...@gmail.com wrote: The logic is actually simple. Tot if we mark in some way an element when it's scanned, we can find the missing numbers in the second scannin. 3,5,1,2,9,10,8,6 When for loop sees '3' it knows elt 3 is there. So multiplies the number at 3rd position by some arbitrary number. (* I've taken the arbitrary number to be n here but CORRECT ONE IS n+3 cos n will fail in some cases* ) so, when it sees '5' multiplies the number at 5th position by n+3. It skips when the numbr is greater than n. n+3 = 11 here. So,after first loop, 33, 55, 11, 2 , 99, 110, 8, 66. So now, in the second scan, the indices of all elts that are divisible by n+3 are present in the array. elts at 4th and 7th positions are not divisible. hence missing numbers are 4 and 7. -- Reduce, Reuse and Recycle Regards, Vivek.S --~--~-~--~~~---~--~~ You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@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 -~--~~~~--~~--~--~---
[algogeeks] Re: Missing numbers
cant u use a string yaar.fruity gethu thaan On Fri, Jul 31, 2009 at 9:57 PM, Vivek S s.vivek.ra...@gmail.com wrote: N! overflows... Try to write a program to find the value of 30! You don't have a variable that is large enough to store such a big number... 2009/7/31 sharad kumar aryansmit3...@gmail.com check this out Let x and y be the missing number, Now equation 1 is : x + y = [n(n+1)/2] - S equation 2 is: x * y = N! /P solve both we get elements On Fri, Jul 31, 2009 at 8:27 PM, Devi G devs...@gmail.com wrote: The logic is actually simple. Tot if we mark in some way an element when it's scanned, we can find the missing numbers in the second scannin. 3,5,1,2,9,10,8,6 When for loop sees '3' it knows elt 3 is there. So multiplies the number at 3rd position by some arbitrary number. (* I've taken the arbitrary number to be n here but CORRECT ONE IS n+3 cos n will fail in some cases *) so, when it sees '5' multiplies the number at 5th position by n+3. It skips when the numbr is greater than n. n+3 = 11 here. So,after first loop, 33, 55, 11, 2 , 99, 110, 8, 66. So now, in the second scan, the indices of all elts that are divisible by n+3 are present in the array. elts at 4th and 7th positions are not divisible. hence missing numbers are 4 and 7. -- Reduce, Reuse and Recycle Regards, Vivek.S --~--~-~--~~~---~--~~ You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@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 -~--~~~~--~~--~--~---
[algogeeks] Re: Missing numbers
appadi partha vikram solutiona la square number ke variable kadeyathu wen n is very large On Sat, Aug 1, 2009 at 7:32 AM, sharad kumar aryansmit3...@gmail.comwrote: cant u use a string yaar.fruity gethu thaan On Fri, Jul 31, 2009 at 9:57 PM, Vivek S s.vivek.ra...@gmail.com wrote: N! overflows... Try to write a program to find the value of 30! You don't have a variable that is large enough to store such a big number... 2009/7/31 sharad kumar aryansmit3...@gmail.com check this out Let x and y be the missing number, Now equation 1 is : x + y = [n(n+1)/2] - S equation 2 is: x * y = N! /P solve both we get elements On Fri, Jul 31, 2009 at 8:27 PM, Devi G devs...@gmail.com wrote: The logic is actually simple. Tot if we mark in some way an element when it's scanned, we can find the missing numbers in the second scannin. 3,5,1,2,9,10,8,6 When for loop sees '3' it knows elt 3 is there. So multiplies the number at 3rd position by some arbitrary number. (* I've taken the arbitrary number to be n here but CORRECT ONE IS n+3 cos n will fail in some cases *) so, when it sees '5' multiplies the number at 5th position by n+3. It skips when the numbr is greater than n. n+3 = 11 here. So,after first loop, 33, 55, 11, 2 , 99, 110, 8, 66. So now, in the second scan, the indices of all elts that are divisible by n+3 are present in the array. elts at 4th and 7th positions are not divisible. hence missing numbers are 4 and 7. -- Reduce, Reuse and Recycle Regards, Vivek.S --~--~-~--~~~---~--~~ You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@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 -~--~~~~--~~--~--~---
[algogeeks] Re: Missing numbers
*for i=1 to sumofXY/2* *if (xorofXY XOR i XOR (sumofXY-i)) is zero* *then x is i, y is (sumofXY-i)* *endfor* Channa, is this logic based on the assumption/fact that no other other pair of numbers (m, n) can have the same XOR and SUMMATION as that of the (x, y) pair? If so, could you please explain it? On Thu, Jul 30, 2009 at 12:04 AM, Prabhanjan ananth prabzy@gmail.comwrote: Let the 2 missing numbers be a and b . Let the sum of the 2 missing numbers be S , product be P . a+b=S -(1) ab=P -(2) Solve (1) and (2) On Wed, Jul 29, 2009 at 7:30 PM, Vikram Sridar vikramsridar...@gmail.comwrote: nice one channa.. much like my solution.. same complexity n memory requiements but pulling that wonderful use of the Xor gate was great show indeed.. very impressive solution --~--~-~--~~~---~--~~ You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@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 -~--~~~~--~~--~--~---
[algogeeks] Re: Missing numbers
Good catch, Vikram. I had a wrong assumption that the pair (i, sumofXY-i) would uniquely match with xorofXY. Here is a counter example to disprove my solution. Suppose X is 5 (binary 101) and Y is 6 (b 110), whose XOR would be 3 (b 011). But, moving unit bit from 5 to 6, we have a pair 4 (100) and 7 (111), which also has the same sum and same XOR. Hence the disproof! I wanted to avoid multiplication and leverage XOR, but overlooked a subtle property. Is there really a way to leverage XOR for this problem? Note: The SOLUTION I posted before for this problem is WRONG. My apologies! Thanks, Channa On Thu, Jul 30, 2009 at 12:51 PM, Vikram Venkatesan s.venkat.vik...@gmail.com wrote: *for i=1 to sumofXY/2* *if (xorofXY XOR i XOR (sumofXY-i)) is zero* *then x is i, y is (sumofXY-i)* *endfor* Channa, is this logic based on the assumption/fact that no other other pair of numbers (m, n) can have the same XOR and SUMMATION as that of the (x, y) pair? If so, could you please explain it? On Thu, Jul 30, 2009 at 12:04 AM, Prabhanjan ananth prabzy@gmail.comwrote: Let the 2 missing numbers be a and b . Let the sum of the 2 missing numbers be S , product be P . a+b=S -(1) ab=P -(2) Solve (1) and (2) On Wed, Jul 29, 2009 at 7:30 PM, Vikram Sridar vikramsridar...@gmail.com wrote: nice one channa.. much like my solution.. same complexity n memory requiements but pulling that wonderful use of the Xor gate was great show indeed.. very impressive solution --~--~-~--~~~---~--~~ You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@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 -~--~~~~--~~--~--~---
[algogeeks] Re: Missing numbers
take an array of n elements.Initially all zero.Traverse the given array and mark the corresponding no as 1. At last traverse again and entr which is zero still is out Answer. Time -O(n) Space O(n) Thanks Regards: Ankit Gupta Marie von Ebner-Eschenbachhttp://www.brainyquote.com/quotes/authors/m/marie_von_ebnereschenbac.html - Even a stopped clock is right twice a day. On Wed, Jul 29, 2009 at 6:26 AM, Channa Bankapur channabanka...@gmail.comwrote: Here is a pseudocode for one of the solutions sumN = sum of all the elements of the arraysumN2 = sum of 1 to (n+2) sumofXY = sumN2 - sumN /*sum of the interested integers, say x, y*/ xorN = XOR of all the elements of the array xorN2 = XOR of 1 to (n+2) xorofXY = xorN XOR xorN2 /*XOR of x, y*/ for i=1 to sumofXY/2 if (xorofXY XOR i XOR (sumofXY-i)) is zero then x is i, y is (sumofXY-i) endfor This solution has running time complexity of O(n) and needs constant extra space. Thanks, Channa On Wed, Jul 29, 2009 at 5:57 PM, Ajinkya Kale kaleajin...@gmail.comwrote: use hashing. On Wed, Jul 29, 2009 at 4:50 PM, Vijayasarathy K vijaykan@gmail.comwrote: Consider an array of 'n' elements which contains all except 2 numbers from 1(n + 2). How can we find the 2 missing elements? -- Ciao, Ajinkya --~--~-~--~~~---~--~~ You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@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 -~--~~~~--~~--~--~---
[algogeeks] Re: Missing numbers
If the array is sorted you can use binary search. First divide the interval until you find an element for which array [mid] == mid+1. Then use binary search again: the first number is left of mid the second is right of mid On Jul 29, 1:20 pm, Vijayasarathy K vijaykan@gmail.com wrote: Consider an array of 'n' elements which contains all except 2 numbers from 1(n + 2). How can we find the 2 missing elements? --~--~-~--~~~---~--~~ You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@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 -~--~~~~--~~--~--~---
[algogeeks] Re: Missing numbers
for(i=1; i=n ;i++ ) //for ease of understanding starting the
array with 1.
{
if(a[ i ] n )
continue;
else
a[ a [ i ] ]*=n;
}
int x[2], m = 0;
for ( int i = 1; i =n ; i++)
{
if(a[ i ] % n == 0)
continue;
else
{
x[m++ ] = i;
if(m == 2) break;
}
}
x[] now contain the two missing numbers in ascending order.
--~--~-~--~~~---~--~~
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algogeeks@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
-~--~~~~--~~--~--~---
[algogeeks] Re: Missing numbers
I'm sorry.. misunderstood the problem and tot the missin numbers are to
be less than n.
Yet it can be modified to suit the pbm.
Suppose the two missin numbers are greater than n, then m==0 when exitin the
loop.
So they will be n+1 and n+2 only.
in case, one of the missin numbers is greater than n, then m==1, and can be
simply found by subtracting the (array_sum+x[0] ) from (sumof 1 to n+2)
numbers.
On Thu, Jul 30, 2009 at 10:55 PM, Devi G devs...@gmail.com wrote:
for(i=1; i=n ;i++ ) //for ease of understanding starting the
array with 1.
{
if(a[ i ] n )
continue;
else
a[ a [ i ] ]*=n;
}
int x[2], m = 0;
for ( int i = 1; i =n ; i++)
{
if(a[ i ] % n == 0)
continue;
else
{
x[m++ ] = i;
if(m == 2) break;
}
}
x[] now contain the two missing numbers in ascending order.
--~--~-~--~~~---~--~~
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algogeeks@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
-~--~~~~--~~--~--~---
[algogeeks] Re: Missing numbers
use hashing. On Wed, Jul 29, 2009 at 4:50 PM, Vijayasarathy K vijaykan@gmail.comwrote: Consider an array of 'n' elements which contains all except 2 numbers from 1(n + 2). How can we find the 2 missing elements? -- Ciao, Ajinkya --~--~-~--~~~---~--~~ You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@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 -~--~~~~--~~--~--~---
[algogeeks] Re: Missing numbers
ok.. great question find the sum of the series , and the squares of the elements in the series Let Sum = S Sum of squares = P now find the sum of the of all numbers from 1... (n+2) and their squares, Let these be A= (n+2)(n+3)/2 (for n = (n)(n+1)/2) B= (n+2)(n+3)(2n+5)/6(for n = (n)(n+1)(2n+1)/6) therefore, v can deduce that X + Y = A - S X^2 + Y^2 = B - P you got 2 equations, solve them --~--~-~--~~~---~--~~ You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@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 -~--~~~~--~~--~--~---
[algogeeks] Re: Missing numbers
Here is a pseudocode for one of the solutions sumN = sum of all the elements of the arraysumN2 = sum of 1 to (n+2) sumofXY = sumN2 - sumN /*sum of the interested integers, say x, y*/ xorN = XOR of all the elements of the array xorN2 = XOR of 1 to (n+2) xorofXY = xorN XOR xorN2 /*XOR of x, y*/ for i=1 to sumofXY/2 if (xorofXY XOR i XOR (sumofXY-i)) is zero then x is i, y is (sumofXY-i) endfor This solution has running time complexity of O(n) and needs constant extra space. Thanks, Channa On Wed, Jul 29, 2009 at 5:57 PM, Ajinkya Kale kaleajin...@gmail.com wrote: use hashing. On Wed, Jul 29, 2009 at 4:50 PM, Vijayasarathy K vijaykan@gmail.comwrote: Consider an array of 'n' elements which contains all except 2 numbers from 1(n + 2). How can we find the 2 missing elements? -- Ciao, Ajinkya --~--~-~--~~~---~--~~ You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@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 -~--~~~~--~~--~--~---
[algogeeks] Re: Missing numbers
nice one channa.. much like my solution.. same complexity n memory requiements but pulling that wonderful use of the Xor gate was great show indeed.. very impressive solution --~--~-~--~~~---~--~~ You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@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 -~--~~~~--~~--~--~---
[algogeeks] Re: Missing numbers
Let the 2 missing numbers be a and b . Let the sum of the 2 missing numbers be S , product be P . a+b=S -(1) ab=P -(2) Solve (1) and (2) On Wed, Jul 29, 2009 at 7:30 PM, Vikram Sridar vikramsridar...@gmail.comwrote: nice one channa.. much like my solution.. same complexity n memory requiements but pulling that wonderful use of the Xor gate was great show indeed.. very impressive solution --~--~-~--~~~---~--~~ You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@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 -~--~~~~--~~--~--~---
