Re: [algogeeks] post and pre increment operators
@priya, Generally printf evaluation starts from left to right so first a++ using post increments assign the value of 3rd %d to be 2 then a++gets evaluated , now a value is 3 2nd %d takes a value as 3 1st %d takes a value as 3 if it is a preincrement like ++a in the third place the output will be 3,3,3... got it i guess... Thanks, Kartheek. On Sun, Jan 9, 2011 at 10:38 AM, priya mehta priya.mehta...@gmail.comwrote: int a=2; printf(%d %d %d,a,a,a++); the output is 3 3 2 can someone tell the logic behind 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.comalgogeeks%2bunsubscr...@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] post and pre increment operators
small correction printf evaluation starts from right to left. On Sun, Jan 9, 2011 at 10:59 AM, kartheek muthyala kartheek0...@gmail.comwrote: @priya, Generally printf evaluation starts from left to right so first a++ using post increments assign the value of 3rd %d to be 2 then a++gets evaluated , now a value is 3 2nd %d takes a value as 3 1st %d takes a value as 3 if it is a preincrement like ++a in the third place the output will be 3,3,3... got it i guess... Thanks, Kartheek. On Sun, Jan 9, 2011 at 10:38 AM, priya mehta priya.mehta...@gmail.comwrote: int a=2; printf(%d %d %d,a,a,a++); the output is 3 3 2 can someone tell the logic behind 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.comalgogeeks%2bunsubscr...@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] post and pre increment operators
Yeah you might be knowing how the expression evaluators work using stack right. printf also uses the same approach On Sun, Jan 9, 2011 at 11:06 AM, priya mehta priya.mehta...@gmail.comwrote: @kartheek so does it use stack for that? On Sun, Jan 9, 2011 at 11:03 AM, priya mehta priya.mehta...@gmail.comwrote: ok i got that On Sun, Jan 9, 2011 at 11:01 AM, kartheek muthyala kartheek0...@gmail.com wrote: small correction printf evaluation starts from right to left. On Sun, Jan 9, 2011 at 10:59 AM, kartheek muthyala kartheek0...@gmail.com wrote: @priya, Generally printf evaluation starts from left to right so first a++ using post increments assign the value of 3rd %d to be 2 then a++gets evaluated , now a value is 3 2nd %d takes a value as 3 1st %d takes a value as 3 if it is a preincrement like ++a in the third place the output will be 3,3,3... got it i guess... Thanks, Kartheek. On Sun, Jan 9, 2011 at 10:38 AM, priya mehta priya.mehta...@gmail.comwrote: int a=2; printf(%d %d %d,a,a,a++); the output is 3 3 2 can someone tell the logic behind 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.comalgogeeks%2bunsubscr...@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.comalgogeeks%2bunsubscr...@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.comalgogeeks%2bunsubscr...@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] help required...
@coolfrog,
What I meant by remained is
Considering your case of A,B,C,D and B is the celebrity,
The sequence is
First A,B ask the question to A, then remained=B
Then B,C ask the question to B, then remained=B
Then B,D ask the question to B, then remained= B
Then ask A,C,D whether they know B
Then ask B whether they know A,C,D
So, that's how I said 3(n-1) questions...
Correct me if I am wrong
On Thu, Sep 23, 2010 at 8:32 PM, coolfrog$
dixit.coolfrog.div...@gmail.comwrote:
@kartheek
i am getting. this prudent approach
but what is add what remained to the remainder.
suppose u have A,B,C,D and B is celebrity ...
if( A knows B)
{ A is not celb.
if( B knows C){}
else{ C is not celb.
if (C knows B )
{ if( D knows B)
{ D is not celb.
only B remain... hence it celeb...
/* suppose if u have A,B,C,D,E
and B is celeb.
then again if (E knows B)
{E is not
celb
only B
remain... hence it celeb...
}
*/
}
}
}
}
look in every if condition we are Asking Sequentially to A
,B,C,D,E...
can these be correct solution
correct me plz... if wrong..
On Thu, Sep 23, 2010 at 12:56 AM, kartheek muthyala
kartheek0...@gmail.com wrote:
Take 2 persons, suppose say A and B
ask one of them the question about other
if A Knows B, then A cannot be the celebrity,
if A does not know B, then B cannot be the celebrity.
add what remained to the remainder.
repeat this process for the remaining n-1 until one or none remained.
Then if it is none then there is no celebrity.
If there is one ask the question whether this person is known by remaining
n-1 and this person does n't know the remaining n-1. So a total of 3(n-1)
questions is used to determine the celeb.
Time complexity is O(n).
Repeat this for the remaining n-1 persons, if the remainder contain one
then
On Wed, Sep 22, 2010 at 9:37 PM, Divesh Dixit
dixit.coolfrog.div...@gmail.com wrote:
Among n people, a celebrity is defined as someone who is known to
everyone, but who knows no
one. Design and analyze to identify the celebrity, if one exists, by
asking only questions of the
following form: Excuse me, do you know person x? You will get a
binary answer for each such
question asked. Find the celebrity by asking only O(n) questions.
--
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.comalgogeeks%2bunsubscr...@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.comalgogeeks%2bunsubscr...@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.comalgogeeks%2bunsubscr...@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] help required...
Take 2 persons, suppose say A and B ask one of them the question about other if A Knows B, then A cannot be the celebrity, if A does not know B, then B cannot be the celebrity. add what remained to the remainder. repeat this process for the remaining n-1 until one or none remained. Then if it is none then there is no celebrity. If there is one ask the question whether this person is known by remaining n-1 and this person does n't know the remaining n-1. So a total of 3(n-1) questions is used to determine the celeb. Time complexity is O(n). Repeat this for the remaining n-1 persons, if the remainder contain one then On Wed, Sep 22, 2010 at 9:37 PM, Divesh Dixit dixit.coolfrog.div...@gmail.com wrote: Among n people, a celebrity is defined as someone who is known to everyone, but who knows no one. Design and analyze to identify the celebrity, if one exists, by asking only questions of the following form: Excuse me, do you know person x? You will get a binary answer for each such question asked. Find the celebrity by asking only O(n) questions. -- 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.comalgogeeks%2bunsubscr...@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: Array Good One!!!!!!!!!!!!!!!!!!!!!!
Thanks for clearing
On Tue, Sep 21, 2010 at 1:58 PM, Naveen Agrawal nav.coo...@gmail.comwrote:
@Kartheek
Ashish algo is perfectly workingBy making before[0]after[length-1]=1
the array is shifted ,which prevents the inclusion of current index.
Ex:
int a[5]={10,4,8,3,9}
before[0]=1
before[1]=10
before[2]=40
before[3]=320
before[4]=960
after[4]=1
after[3]=9
after[2]=27
after[1]=216
after[0]=864
ans[0]= ( before[0]=1 )*(after[0]=864)
.
.
.
similarly others
-
Naveen
--
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.comalgogeeks%2bunsubscr...@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: point lies inside or outside of triangle..
@gene i didn't understand the boolean thing in your algo,
Say triangle is ABC, say Point is p
Algo goes like this,
for side AB
1. calculate cross product of(p-A)*(B-A)[ Which is nothing but the side
function in gene algo] See the sign.
2. calculate the cross product of (C-A)*(B-A) . See the sign if it is not
same then say the point lies outside.
3. If the signs are same repeat the step1 from other sides.
The funda here is if a point is inside a triangle then cross product of the
point joining any vertex to the side containing that vertex, should point in
the same side (up or below), with reference to cross product of this vertex
to any reference point(C for AB because they are in the same plane) with the
side (AB) should also point in the same direction, When this process is
repeated for all sides then we can say that the point is inside the
triangle.
On Tue, Sep 21, 2010 at 6:09 AM, Gene gene.ress...@gmail.com wrote:
This is okay, but does more math than necessary. Here's another
approach:
// Return 0 if p is left of a-b, 2 if right of a-b, and 1 if on a-
b.
int side(PT *p, PT *a, PT *b)
{
float d = (p.x-a.x) * (b.y-a.y) - (p.y-a.y) * (b.x-a.x);
return d 0 ? 0 : d 0 ? 2 : 1;
}
// This table treats points on the edges as inside. Just redo the
// table to count them as outside.
bool inside_polygon(PT *p, PT *a, PT *b, PT *c)
{
bool p[3][3][3] =
{{ // 0, ...
// 0 =00
{ true, true, false }, // 0, ...
{ true, true, false }, // =0
{ false, false, false }}, // 0
{{ // =0,
{ true, true, false }, // 0
{ true, true, true }, // =0
{ false, true, true }}, // 0
{{ // 0,
{ false, false, false }, // 0
{ false, true, true }, // =0
{ false, true, true }}}; // 0
return p[side(p, a, b)][side(p, b, c)][side(p, c, a)];
}
This relies on the facts 1) if a, b, c if abc are given in CCW order,
then all three side values are 0 iff the point is inside; and 2) if
they are given in CW order, then the side values are 2 iff the point
is inside; 3) the values can't be 000 if the vertices are in CCW order
(except for the point at infinity, which doesn't exist in a computer);
and 4) the values can't be 222 if the vertices are given in CW order
(again except for the point at infinity).
On Sep 20, 4:20 pm, Naveen Agrawal nav.coo...@gmail.com wrote:
Take intersection point of triangle as a,b,c
And the testing point as p
boolean SameSide(p,s,t ,u)
if s p lies on same side //to check same side form equation
using t and u and then evaluate the value of point
return true//ps,if both gives same
sign(+ve or -ve) value then they are on same side
else
return false
void PointInTriangle(p, a,b,c)
if (SameSide(p,a, b,c) SameSide(p,b, a,c) SameSide(p,c, a,b))
Inside the triange
else
outside triangle
--
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.comalgogeeks%2bunsubscr...@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: Array Good One!!!!!!!!!!!!!!!!!!!!!!
I guess before[index] should contain product of the numbers before index and after[index] should contain all the product after the index but @Ashish algo isn't that before[index] contains product that includes the number at the index position also. Please clarify me... On Sun, Sep 19, 2010 at 9:27 PM, Minotauraus anike...@gmail.com wrote: It's been discussed here before. Start by multiplying from either sides of the array and stop when both pointers reach the opposite side. takes O(n) time and does not involve division so won't crap out for cases where some of the elements are 0. I was asked this for my Google phone screen I wish I knew this^ back then. On Sep 19, 7:48 am, bittu shashank7andr...@gmail.com wrote: Given an array of numbers, replace each number with the product of all the numbers in the array except the number itself *without* using division. -- 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.comalgogeeks%2bunsubscr...@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: Finding max for all positions of a moving window
@Minotauraus, if we consider your scenario, 10 12 14 9 23 2 4 6 9 19 22 10 6 12 10 for 1st window max=23 second window max=23(2322) third windw max=23(2310) fourth window max=23(236) fifth window max=23(2312) sixth window max =22(calculate the maximum in the window). repeat again So the number of moves in which the process is repeated depends on the index of the maximum element.(may not be 10 moves everytime) Correct me if i am wrong. On Sun, Sep 19, 2010 at 9:38 PM, Minotauraus anike...@gmail.com wrote: You don't need any data structure. Since the window moves by one element each, you can simply count 10 such moves and compare each new element with currMax. If it's greater, overwrite currMax. After 10 moves you have your max for that 10 element window, rinse and repeat. On Sep 17, 1:31 am, Navin Naidu navinmna...@gmail.com wrote: Use Max-Heap, add first ten elements, the root element will be max, Next Iteration, remove a[0] and add a[10], max-heapify. On Fri, Sep 17, 2010 at 1:48 PM, Tech Id tech.login@gmail.com wrote: You have an array of 100 integers. There is a window of 10 elements which starts from 0th element and moves by 1 element till the 90th element. We need to print the maximum element for all the positions of the window. Hint: For the first position of the window, you have to find the maximum as done normally for any array. After that, when the window moves by 1 element, you just have to consider one more element and forget the very first element to find the new maximum. Thus, after the first max, it should take much less time to find the max for all the other window positions. -- 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.comalgogeeks%2bunsubscr...@googlegroups.com algogeeks%2bunsubscr...@googlegroups .com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- Thanks Regards, - NMN -- 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.comalgogeeks%2bunsubscr...@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
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 akki12...@gmail.com 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 dedhriti...@gmail.com
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 bansal...@gmail.com
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 dave_and_da...@juno.com 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 raj.jagvan...@gmail.com 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.comalgogeeks%2bunsubscr...@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.comalgogeeks%2bunsubscr...@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.comalgogeeks%2bunsubscr...@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.comalgogeeks%2bunsubscr...@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
Re: [algogeeks] Re: find duplicate and missing element
@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 akki12...@gmail.com 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
kartheek0...@gmail.com 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 akki12...@gmail.com
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 dedhriti...@gmail.com
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 bansal...@gmail.com
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 dave_and_da...@juno.com
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 raj.jagvan...@gmail.com 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.comalgogeeks%2bunsubscr...@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.comalgogeeks%2bunsubscr...@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
