@sagar and @brijesh: awesome explanation!!! too good! 1 doubt!
the question says it has only 28 leaves. According to uour explanations, it
has 81 leaves. how is it possible??
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this
It could have a maximum of 81 leaves with the same '40' no of internal
nodes so for any value between 28 to 81, it would have only 40 internal
nodes
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To view this discussion on the web visit
Excatly
why dont u just make a rough diagram in paper for binary and ternary trees
and just see that each level has max of 2/3^i where 2/3 is for
binary/ternary tree and i is level where root level is 0...
then make a complete ternary tree and see why leaves with 28 in numbers have
@Sagar
See at level 4, 81 leaf nodes are possible, since in question it has been
given 28 leaf nodes, if i use just 10 nodes from level 3 (27 nodes), i can
get 28 leaves, but if u observe the remaining 17 nodes in the 3rd level are
also becoming leaf nodes, but in question given as 28 leaf
ya ur right!!!
On 10 August 2011 18:44, vamshi vijay vamshi1...@gmail.com wrote:
@Sagar
See at level 4, 81 leaf nodes are possible, since in question it has been
given 28 leaf nodes, if i use just 10 nodes from level 3 (27 nodes), i can
get 28 leaves, but if u observe the remaining 17
gr8 work vamshi
but total nodes will be
1+3+9+27+*2*(not 1)=42
On Wed, Aug 10, 2011 at 6:59 PM, Pratz mary pratima.m...@gmail.com wrote:
ya ur right!!!
On 10 August 2011 18:44, vamshi vijay vamshi1...@gmail.com wrote:
@Sagar
See at level 4, 81 leaf nodes are possible, since in
@sagar: Thanks again :) But my doubt is it'll have more than 28 leaf nodes
when the ques clearly sayd it shud have 28 leaf nodes.
@vamshi: I kind of agree with what you say.
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this
I am just increasing the size of the current string by one. So that a
new character can be appended.
On Sat, Aug 6, 2011 at 11:01 AM, Tushar Bindal tushicom...@gmail.com wrote:
@gaurav
didn't get this:
Just to increase the size of the string by one.
Then you can put any character at the the
In a ternary Tree No of leaves 28. How many nodes it have?
An AVL tree with height d. How many children it have?
--
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
1.28+27
2.2pow(d)
On Wed, Aug 10, 2011 at 12:07 AM, NIKHIL nikhil.jain.shali...@gmail.comwrote:
In a ternary Tree No of leaves 28. How many nodes it have?
An AVL tree with height d. How many children it have?
--
You received this message because you are subscribed to the Google
in ques 1 i considered leaves as nodes... if we consider only internal nodes
then it have 27
On Wed, Aug 10, 2011 at 1:12 AM, sagar pareek sagarpar...@gmail.com wrote:
1.28+27
2.2pow(d)
On Wed, Aug 10, 2011 at 12:07 AM, NIKHIL
nikhil.jain.shali...@gmail.comwrote:
In a ternary
pls explain how u got 27?
*Muthuraj R
IV th Year , ISE
PESIT , Bangalore*
On Wed, Aug 10, 2011 at 1:13 AM, sagar pareek sagarpar...@gmail.com wrote:
in ques 1 i considered leaves as nodes... if we consider only internal
nodes then it have 27
On Wed, Aug 10, 2011 at 1:12 AM, sagar pareek
I dont think 27 is the right answer,... it should be log 28 /log 3... i mean
log 28 base 3 shuold be the no. of internal nodes ! and for any no of
leaves , 2781, the answer would be same...
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks
sorry answer is not 27 its *80*
just consider a binary tree 1st
root has nodes 2^0=1
1st level has 2^1=2
2nd has 2^2=4
so nth level has leaves 2^n
now if we have ternary tree
then follow same procedure just change 3 with 2..
mean at nth level total leaves 3^n
now calculate the level
80??? how can 80 internal nodes just produce only maximum of 81 leaves and
that too in 3ary tree
the answer is 1+3+9+27 = 40 internal nodes... think like this
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To view this discussion on
1 produces 3 nodes , which then 9 nodes,-- 27 nodes , and thses 27
nodes finally produces =81 leaves so sum of 27+9+3+1= 40 is the right
answer... i guess
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To view this discussion on the web
General approach would be , get the no of levels first by log 28 /log 3 , =
4(use ceiling)...and now 3^0+3^1+3^2+3^3 = 40 will be no of internal nodes..
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To view this discussion on the web visit
Oh!
sorry
my idea for internal nodes=leaves-1 is only for binary tree
like at level 4 total leaves 2^4=32
so internal nodes=32-1=31
also can be checked as 16+8+4+2+1=31
there must be a shortcut for ternary also...
by the way brijesh thanks for correcting me.
so total internal nodes will be 40
what if the alphabet is {a,b,c,d} and we have to print substrings of length
2 or 3 ?
On Sat, Aug 6, 2011 at 11:01 AM, Tushar Bindal tushicom...@gmail.comwrote:
@gaurav
didn't get this:
Just to increase the size of the string by one.
Then you can put any character at the the new last
ohh my bad... it is working fine for all cases :)
On Sat, Aug 6, 2011 at 11:56 AM, mohit verma mohit89m...@gmail.com wrote:
what if the alphabet is {a,b,c,d} and we have to print substrings of length
2 or 3 ?
On Sat, Aug 6, 2011 at 11:01 AM, Tushar Bindal tushicom...@gmail.comwrote:
given a set of letters and a length N, produce all possible output.(Not
permutation). For example, give the letter (p,o) and length of 3, produce
the following output(in any order you want, not just my example order)
ppp ppo poo pop opp opo oop ooo
another example would be given (a,b) and length
A *trie *could help here where the number of children for each node matches
the required length.
On Fri, Aug 5, 2011 at 12:20 PM, Kamakshii Aggarwal
kamakshi...@gmail.comwrote:
given a set of letters and a length N, produce all possible output.(Not
permutation). For example, give the letter
On Fri, Aug 5, 2011 at 12:20 PM, Kamakshii Aggarwal
kamakshi...@gmail.com wrote:
given a set of letters and a length N, produce all possible output.(Not
permutation). For example, give the letter (p,o) and length of 3, produce
the following output(in any order you want, not just my example
@gaurav:i could not understand ur sol.can u explain it again..
On Fri, Aug 5, 2011 at 12:32 PM, Gaurav Menghani
gaurav.mengh...@gmail.comwrote:
On Fri, Aug 5, 2011 at 12:20 PM, Kamakshii Aggarwal
kamakshi...@gmail.com wrote:
given a set of letters and a length N, produce all possible
The basic idea is that for every position of the string, you fill it
with all possible alphabets in your set of allowed alphabets, let the
set be called alphabet.
Now, you can do this recursively.
backtrack(s,l) denotes, a string s has been formed, and is of length
l. Now we need to add more
as an eg.
let ab be the string, and 3 characters length string is wht is expected..
a - -
b - -
a a -
a b -
b a -
b b -
a a a
a a b
a b a
a b b
b a a
b a b
b b a
b b b
On Fri, Aug 5, 2011 at 12:49 PM, Gaurav Menghani
gaurav.mengh...@gmail.comwrote:
The basic idea is that for every
An Implementation:
#includeiostream
#includestring
using namespace std;
string alphabet;
int maxlen;
void backtrack(string s,int l)
{
if(l==maxlen) { coutsendl; return; }
s.push_back('-');
for(int i=0;ialphabet.size();i++)
{ s[l]=alphabet[i]; backtrack(s,l+1); }
}
int main()
{
Or one could just simulate a counting from 0 to (numchars^N)-1 in base
numchars.
...
code:
void printit(int N,char chars[],int index[]){
for(int i=0;iN;i++){
printf(%c,chars[index[i]]);
}
printf(\n);
}
void generate(int numchars,char chars[],int N){
int index[100]={0};
I think it can be done using bitwise ANDing with a mask
On Fri, Aug 5, 2011 at 12:58 PM, Gaurav Menghani
gaurav.mengh...@gmail.com wrote:
An Implementation:
#includeiostream
#includestring
using namespace std;
string alphabet;
int maxlen;
void backtrack(string s,int l)
{
if(l==maxlen)
@gaurav:can u please explain what is the purpose of this line..
s.push_back('-');
On Fri, Aug 5, 2011 at 1:10 PM, Nitin Nizhawan nitin.nizha...@gmail.comwrote:
Or one could just simulate a counting from 0 to (numchars^N)-1 in base
numchars.
...
code:
void printit(int N,char chars[],int
Just to increase the size of the string by one.
Then you can put any character at the the new last position, which is 'l'.
On Fri, Aug 5, 2011 at 2:34 PM, Kamakshii Aggarwal
kamakshi...@gmail.com wrote:
@gaurav:can u please explain what is the purpose of this line..
s.push_back('-');
On Fri,
Great.
On Fri, Aug 5, 2011 at 2:42 PM, Kamakshii Aggarwal
kamakshi...@gmail.com wrote:
@gaurav:i got it..thanks for the solution
On Fri, Aug 5, 2011 at 2:34 PM, Kamakshii Aggarwal kamakshi...@gmail.com
wrote:
@gaurav:can u please explain what is the purpose of this line..
s.push_back('-');
Even if the number of elements is more than two, it is possible with
bitwise operations, but it gets clumsy.
Suppose your alphabet has 4 characters. You can either:
- Count from 0 to (14*n)-1 and use four bits to denote the selection
of the alphabet. Also, only one bit amongst those four should
Ok, Thanks
On Fri, Aug 5, 2011 at 2:53 PM, Gaurav Menghani
gaurav.mengh...@gmail.comwrote:
Even if the number of elements is more than two, it is possible with
bitwise operations, but it gets clumsy.
Suppose your alphabet has 4 characters. You can either:
- Count from 0 to (14*n)-1 and use
@gaurav
didn't get this:
Just to increase the size of the string by one.
Then you can put any character at the the new last position, which is 'l'.
can u pls explain that?
On Fri, Aug 5, 2011 at 2:57 PM, Nitin Nizhawan nitin.nizha...@gmail.comwrote:
Ok, Thanks
On Fri, Aug 5, 2011 at 2:53
35 matches
Mail list logo