claudio.corsi
BAN USERNo sorry. Forget my latest comment.
Full btree with n leaves has 2N - 1 nodes. So, a full btree with N nodes has (n + 1)/2 leaves. So, we have to calculate the Catalan number of (n-1)/2, that is (n+1)/2 - 1.
see en.wikipedia.org/wiki/Catalan_number#Applications_in_combinatorics
The Catalan number Cn is the number of full btree having n+1 leaves.
A full btree with N nodes has 2n - 1 leaves. So the number of full btrees with N nodes is C(2n-1), i.e. the Catalan number of 2n - 2.
Errata corrige:
2) for each i in i - n: b[i] = Math.pow(2, L - log(b[i]));
is
2) for each i in (0,n-1): b[i] = Math.pow(2, L - log(b[i]));
I think it can be solved with some math.
1) L = sum( log(b[i]) ) for each i - can be done in O(n).
2) for each i in i - n: b[i] = Math.pow(2, L - log(b[i]));
The idea is the following. log(AxBxC) = log(A) + log(A) + log(C) and AxBXC = 2^log(AxBxC). So, log(AxB) is log(A) + log(B) or L - log(C). Then AxB is 2^(L - log(C)).
I'm missing something?
In case you can't use any form of data structure as returning type of the recursive call (a DS to collect in a single tree traversal the number of leafs and inner nodes seen so far), a simple solution may be:
1) count the total number A of nodes in O(n) with a simple tree traversal
2) count the total number B of leafs with a second algorithm - O(n) too
3) return A - B
The global running time is O(n).
I think that a good answer is to send the length of the string in bytes (coded for example as a 4 bytes unsigned integer) followed by the list of bytes, one per char.
The receiver reads the first 4 bytes and understand the string length (let says L), then it reads the following L bytes and build the string.
Here we are assuming that the string is ASCII encoded, so we don't need any other information.
Anyway for completeness, we can encode also the string encoding(ASCII, UTF8, UTF16, ISO*, etc...) using for instance an extra byte after the string length field. In this case the reader reads 4 bytes for the length, 1 byte for the encoding and L bytes for the content. Depending on the encoding the receiver can interpret correctly the string content.
If I understand the question, it is matter to count the number of verttical lines connecting the nodes of the btree.
If this interpretation is correct here a recursive solution based on a hashmap.
Nothe that them map at the end will contains a key for each vertical lines and the list of nodes on that line. If you need the sum of the elements you can iterate over each list.
- claudio.corsi March 16, 2011