Re: [algogeeks] Vertical Sum in a given Binary Tree
plz some one explain...i hav read online but getting the code and same explanaiton...need it urgent...thnx in advance On Sun, Mar 18, 2012 at 12:38 AM, rahul sharma rahul23111...@gmail.comwrote: @anna..plz elaborate more... On Sun, Mar 18, 2012 at 12:26 AM, Supraja Jayakumar suprajasank...@gmail.com wrote: Hi I think its the sum of all the right children of the left subtree and left children of the right subtree. (Note: this does NOT apply recursively) Thanks On Sat, Mar 17, 2012 at 9:31 AM, rahul sharma rahul23111...@gmail.comwrote: plz explain...i m nt able to get the concept. On Sat, Mar 17, 2012 at 8:50 PM, rahul sharma rahul23111...@gmail.comwrote: how come 2,3,7 in vertical sum? On Sat, Mar 17, 2012 at 3:48 PM, prashant thorat prashantnit...@gmail.com wrote: First , Do recursive traverse from root node and assign vertical level for each node. like this, for root node level = 0 , root-left level = -1 , root-left-right = 0 , root-left-left = -2, like this so below tree becomes, 1(0) /\ 2(-1)3(1) / \ /\ 4(-2) 5(0) 6(1) 7(2) After this again, take an array to store sum initialize to 0, and traverse tree again , while traversing store the value of that node in it's level. This way u'll be able to calculate vertical sum. Thanks On Sat, Mar 17, 2012 at 3:29 PM, rahul sharma rahul23111...@gmail.com wrote: what is vertical sum in binayr tree...i dnt need the algo for this..just need the concept...that what is vertical sum??? Given a Binary Tree, find vertical sum of the nodes that are in same vertical line. Print all sums through different vertical lines. Examples: 1 / \ 2 3 / \/ \ 4 5 6 7 The tree has 5 vertical lines Vertical-Line-1 has only one node 4 = vertical sum is 4 Vertical-Line-2: has only one node 2= vertical sum is 2 Vertical-Line-3: has three nodes: 1,5,6 = vertical sum is 1+5+6 = 12 Vertical-Line-4: has only one node 3 = vertical sum is 3 Vertical-Line-5: has only one node 7 = vertical sum is 7 So expected output is 4, 2, 12, 3 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?hl=en. -- Yours affectionately, Prashant Thorat -- 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?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 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?hl=en. -- U -- 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?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 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?hl=en.
Re: [algogeeks] Vertical Sum in a given Binary Tree
Hi
Others are also welcome to comment on the code. If links are allowed in
algogeeks, I might send my wordpress blog link that explains this problem
in detail and in picture.
BinaryTree* VerticalSum(BinaryTree *bt) {
if(!bt) return;
BinaryTree *left = bt-left;
BinaryTree *right = bt-right;
bt-VerticalSumValue += right(left)-value+left(right)-value;
VerticalSum(left);
VerticalSum(right);
}
BinaryTree* right(BinaryTree *left) {
if(!left) return;
sum+=right(left-right);
return sum;
}
BinaryTree *left(BinaryTree *right) {
if(!right) return;
sum+=left(right-left);
return sum;
}
Thanks
Supraja J
On Sun, Mar 18, 2012 at 5:50 AM, rahul sharma rahul23111...@gmail.comwrote:
plz some one explain...i hav read online but getting the code and same
explanaiton...need it urgent...thnx in advance
On Sun, Mar 18, 2012 at 12:38 AM, rahul sharma rahul23111...@gmail.comwrote:
@anna..plz elaborate more...
On Sun, Mar 18, 2012 at 12:26 AM, Supraja Jayakumar
suprajasank...@gmail.com wrote:
Hi
I think its the sum of all the right children of the left subtree and
left children of the right subtree. (Note: this does NOT apply recursively)
Thanks
On Sat, Mar 17, 2012 at 9:31 AM, rahul sharma
rahul23111...@gmail.comwrote:
plz explain...i m nt able to get the concept.
On Sat, Mar 17, 2012 at 8:50 PM, rahul sharma
rahul23111...@gmail.comwrote:
how come 2,3,7 in vertical sum?
On Sat, Mar 17, 2012 at 3:48 PM, prashant thorat
prashantnit...@gmail.com wrote:
First , Do recursive traverse from root node and assign vertical
level for each node. like this,
for root node level = 0 , root-left level = -1 , root-left-right =
0 , root-left-left = -2, like this
so below tree becomes,
1(0)
/\
2(-1)3(1)
/ \ /\
4(-2) 5(0) 6(1) 7(2)
After this again, take an array to store sum initialize to 0, and
traverse tree again , while traversing store the value of that node in
it's
level.
This way u'll be able to calculate vertical sum.
Thanks
On Sat, Mar 17, 2012 at 3:29 PM, rahul sharma
rahul23111...@gmail.com wrote:
what is vertical sum in binayr tree...i dnt need the algo for
this..just need the concept...that what is vertical sum???
Given a Binary Tree, find vertical sum of the nodes that are in same
vertical line. Print all sums through different vertical lines.
Examples:
1
/ \
2 3
/ \/ \
4 5 6 7
The tree has 5 vertical lines
Vertical-Line-1 has only one node 4 = vertical sum is 4
Vertical-Line-2: has only one node 2= vertical sum is 2
Vertical-Line-3: has three nodes: 1,5,6 = vertical sum is 1+5+6 = 12
Vertical-Line-4: has only one node 3 = vertical sum is 3
Vertical-Line-5: has only one node 7 = vertical sum is 7
So expected output is 4, 2, 12, 3 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?hl=en.
--
Yours affectionately,
Prashant Thorat
--
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?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 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?hl=en.
--
U
--
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?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 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?hl=en.
--
U
--
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?hl=en.
Re: [algogeeks] ITRIX'12 OPC
+1 On Fri, Mar 16, 2012 at 11:35 PM, shady sinv...@gmail.com wrote: i wanted to try the questions now, but can't submit, can you provide the problems, and testdata ? On Mon, Mar 12, 2012 at 10:41 PM, Kashyap Krishnakumar kashyap...@gmail.com wrote: Hi, The online programming contest of ITRIX, the national level technical symposium of the Department of Information Sciences and Technology, College of Engineering Guindy is up and running. Prizes worth 15k to be won. Contest page: www.spoj.pl/ITRIX12/ Participate and enjoy the contest. Have fun coding. -- Kashyap.K, III year, B.E CSE, College of Engineering Guindy, Anna University, Chennai. -- If you've never failed, you've never lived! -- 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?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 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?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 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?hl=en.
[algogeeks] Re: remove duplicates
i don't think it's possible (almost sure) On Mar 17, 3:41 pm, rahul sharma rahul23111...@gmail.com wrote: guys do we have algo to remove duplicates in o(n) time and in spce comepexity 0(1)...in unsorted...array or string.??? -- 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?hl=en.
Re: [algogeeks] Re: remove duplicates
possible but with constraints on the range of the numbers On Sun, Mar 18, 2012 at 8:45 PM, rafi rafiwie...@gmail.com wrote: i don't think it's possible (almost sure) On Mar 17, 3:41 pm, rahul sharma rahul23111...@gmail.com wrote: guys do we have algo to remove duplicates in o(n) time and in spce comepexity 0(1)...in unsorted...array or string.??? -- 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?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 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?hl=en.
[algogeeks] Re: Math Question
I'm sorry there's an algebra error below, but fortunately the proof
still works. It should be
From this, algebra provides
10^e - 1 == 0 (mod 9Y) and
10^e == 1 (mod 9Y).
But 9Y and 10^e are still coprime, so we're good.
Here is code that seems to be working fine.
#include stdio.h
int main(int argc, char *argv[])
{
int x, x9, m, p, a, b;
if (argc 1 sscanf(argv[1], %d, x) == 1) {
a = b = 0;
while (x % 2 == 0) {
a++;
x /= 2;
}
while (x % 5 == 0) {
b++;
x /= 5;
}
x9 = 9 * x;
m = 10 % x9;
p = 1;
while (m != 1) {
m = (10 * m) % x9;
p++;
}
printf(divides %d 1's followed by %d 0's\n,
p, a b ? a : b);
}
return 0;
}
For example:
$ ./a.out 45
divides 9 1's followed by 1 0's
$ ./a.out 192
divides 3 1's followed by 6 0's
./a.out 947838840
divides 299910 1's followed by 3 0's
On Mar 16, 4:27 pm, Gene gene.ress...@gmail.com wrote:
Dave, this is very beautiful. Here is a less elegant proof, though it leads
to an efficient algorithm.
In a different problem some time ago, there was a statement that every
number with a 3 in the units position has a multiple that consists of
all 1s. The proof needs a little number theory. Any number Z that is
all 1's can be written as (10^e - 1) / 9 for some integer e. So if Y
is the number we are given (ending in 3), we must find e such that
(10^e - 1) / 9 == 0 (mod Y). From this, algebra provides 10^e - 1 ==
0 (mod Y) and 10^e == 1 (mod Y). Note 10^e and Y are coprime. The
prime factors of the former are all 5 and 2, and since Y ends in 3, it
can have neither of these. Then by Euler's Theorem, e must exist (and
in fact Euler's Totient Function gives its value)! So we are done.
Corollary: a number with 1, 7, or, 9 in the units position also has a
multiple that's all 1s. Proof: Multiply by 3, 9, or 7 respectively to
get a number with 3 in the units position, then use the result above.
The rest:
Let X be the (arbitrary) number we are given. Divide out all its
factors of 2 and 5 to obtain Y.
Claim: Y has 1, 3, 7, or 9 in the units position. Proof: If it ended
with any other digit, it would be divisible by 2 or 5!
Therefore we can find a number Z consisting of all 1's that is a
multiple of Y. Suppose we factored out (2^a)(5^b) above. Then Z
(10^max(a, b)) is a number consisting of all 1's and 0's that is a
multiple of X as desired!
It's not hard to implement in this in time linear to the number of
digits of the multiple (assuming a real RAM model of computation).
Please let me know if you see any problems with this argument.
On Mar 7, 4:32 pm, Don dondod...@gmail.com wrote:
Theorem: In any set of (n+1) distinct integers there exists two whose
difference is divisible by n.
Proof: Each of these integers leaves a remainder between 0 and n-1
inclusive upon division by n. Since there are n possible remainders
and (n+1) integers that means there exist two which have the same
remainder by the PigeonHole Principle. So their difference is
divisible by n.
Theorem: Given any positive integer n there exists a positive number
consisting of only 1's and 0's which is divisible by n.
Proof: Construct the sequence of (n+1) integers:
1,11,111,,111...1
By the first theorem two of these numbers have a difference divisible
by n. That difference will be a number consisting of only 1's and
0's.
On Mar 7, 1:17 pm, karthikeya s karthikeya.a...@gmail.com wrote:
A math problem: Prove that for all positive integer n, there exist at
least
one positive integer whose digits are only 1s and 0s and is divisible
by n.
--
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?hl=en.
Re: [algogeeks] Re: remove duplicates
in a string... yes, because there are only 256 possible characters (or 65536, in case of unicode), so just create a boolean array of length 256 initialized to false and whenever a character occurs make the corresponding element true. While scanning the string, if an element has already appeared, delete it. -- 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?hl=en.
Re: [algogeeks] Re: remove duplicates
sorry, didn't get ? On Sun, Mar 18, 2012 at 11:19 PM, Siddhartha Banerjee thefourrup...@gmail.com wrote: in a string... yes, because there are only 256 possible characters (or 65536, in case of unicode), so just create a boolean array of length 256 initialized to false and whenever a character occurs make the corresponding element true. While scanning the string, if an element has already appeared, delete it. -- 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?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 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?hl=en.
Re: [algogeeks] Google written test
@all : i guess question is on Fibonacci coding.
here you can find the algo :-
http://en.wikipedia.org/wiki/Fibonacci_coding
On Sun, Mar 18, 2012 at 2:58 AM, Atul Singh atulsingh7...@gmail.com wrote:
@Ravi... there should be only one answer as for fibonacci representation
of a number we have to include the part of the fibonacci number just less
than the number then remaining part of the sum is filled by fibonacci
numbers starting from 1
suppose we have to convert 6 into fibonacci representation
then 6 has two sum sets as {1,2,3} or {1,5}
then the fibonacci number just less than 6 is 5 so bit representing 5 is
set then for completing the sum to 6 bit 1 is also set.
so *fibonacci representation of 6 is 1001 .* not 0111
ATul Singh | Final Year | Computer Science Engineering | NIT Jalandhar
| 9530739855 |
--
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?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 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?hl=en.
