No it won't it will just reduce the height of tree to n/2 (from n).
My algo-
1. Parse in triplets. For every 3 nodes make the second one parent of other
two. Also, queue up such parents.
2. repeat step 1 till you have only 1 node left (root).
But this may give a tree 'imbalanced at root. we may n
An edgy case...
On Sun, Aug 1, 2010 at 9:52 AM, Shiv ... wrote:
> What about this-
> =
> long multiply(long num, int n) {
> long bigSum=0;
> while(n>=1) {
> int sum =num; int j*=1*; //to avoid garbage @n=1.
> for(int i =2; i<=n; i= i*
What about this-
=
long multiply(long num, int n) {
long bigSum=0;
while(n>=1) {
int sum =num; int j;
for(int i =2; i<=n; i= i*2) {
sum+=sum;
j=i;
} //for
find the middle of the list and make it as the root..thus i this maner u
will get a balanced tree..
--
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 grou
If suppose
we want to Do N*K
then we add N K-times or K N-times.
hence the complexity should be O(N*K)
On Sat, Jul 31, 2010 at 9:12 PM, Dave wrote:
> If by "repeated addition method," you mean
>
> m + m + m + ... + m (where m occurs k times)
>
> for forming the product k*m, then the work of f
Cant u slit it s n/2 companies and merge them recursively .like x^y the
multiply x to y/2 time and then multiply tht product twice.
On Sat, Jul 31, 2010 at 6:59 PM, sourav wrote:
> Suppose we start with n companies that eventually merge into one big
> company. How many different ways are th
@Ram Kumar: Yes. Simple and affective.
Just at each node:
node->left->side=node->right
node->right->side=node->side->left
i.e at each node you are setting the side of each of your child. Go on and
just do it for all nodes. Done.
On Sat, Jul 31, 2010 at 9:39 AM, Ram Kumar wrote:
> DONT DO A BFS
Multiplying two n digit numbers, where multiplication of two 1 digit numbers
is O(1), is : O(n^2).
On Sat, Jul 31, 2010 at 9:12 PM, Dave wrote:
> If by "repeated addition method," you mean
>
> m + m + m + ... + m (where m occurs k times)
>
> for forming the product k*m, then the work of forming
For merging n companies, F(n) = n*F(n-1) for n > 3.
Base case, F(3) = 3.
On Sat, Jul 31, 2010 at 6:59 PM, sourav wrote:
> Suppose we start with n companies that eventually merge into one big
> company. How many different ways are there for them to merge?
>
> With three companies {a,b,c}, we need
At the moment, I can only think of an O(n^3) algo.
Maybe if you can find a hash function which computes the hash value
depending on the unique characters the string contains, you can reduce it to
O(n^2).
On Sat, Jul 31, 2010 at 7:09 PM, srikanth sg wrote:
> given two string , find the minimum w
A doubly linked list with ordered nodes(increasing order) is a SKEWED BST.
How can we change it into (inplace)balanced BST .
Shrish Mishra NIT,Allahabad
--
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" group.
To post to this group, send email to al
LOL :P
On Sat, Jul 31, 2010 at 8:18 AM, jalaj jaiswal wrote:
> @ abv ... ab to band kar de bhai
>
>
> On Sat, Jul 31, 2010 at 7:09 PM, srikanth sg wrote:
>
>> given two string , find the minimum width in string 1 containing the
>> all characters of string 2 , they may present in different orde
@ abv ... ab to band kar de bhai
On Sat, Jul 31, 2010 at 7:09 PM, srikanth sg wrote:
> given two string , find the minimum width in string 1 containing the
> all characters of string 2 , they may present in different order
> string 1-HELLO
> string 2- LE
> answer-2
>
> --
> You received this mes
Suppose we start with n companies that eventually merge into one big
company. How many different ways are there for them to merge?
With three companies {a,b,c}, we need to find the number of ways that
the three companies can become two companies, and for every one of
those possibilities, the two r
If by "repeated addition method," you mean
m + m + m + ... + m (where m occurs k times)
for forming the product k*m, then the work of forming k*m where k and
m are n digit numbers is O((k-1)*n).
Using the elementary school algorithm, the work can be reduced to
O(n^2).
See http://en.wikipedia.or
O(log n). If u add in pairs. e.g. (5+5)=10. now add 10+10.
On Sat, Jul 31, 2010 at 6:28 PM, sourav wrote:
> When you first learned to multiply numbers, you were told that x * y
> means adding x a total of y times, so 5 * 4 = 5+5+5+5 = 20. What is
> the time complexity of multiplying two n-digi
@Debajyoti. There are 25 possible values of 5*rand5() + rand5(). The
largest multiple of 7 not exceeding 25 is 3*7. Thus, I divide by 3.
The largest number n such that n/3 = 7 is 23. This is where the 3 and
23 come from. You might google "rejection method" to find fuller
descriptions of the theory
@Sony. I took (2/3)*rand5() as if (2/3) was a double. Otherwise,
(2/3)*rand5() = 0*rand5() = 0, which is not what you calculated when
you wrote 2*(i/3) instead of (2/3)*i.
And yes, the fact that the distribution is not uniform does matter,
since we want the results to be uniform. Using your interp
given two string , find the minimum width in string 1 containing the
all characters of string 2 , they may present in different order
string 1-HELLO
string 2- LE
answer-2
--
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" group.
To post to this group,
why u have chosen that 23 ?
why dividing by 3 ?
don't understand the logic.
Please explain so that it become understandable.
On 7/31/10, Dave wrote:
> Use the rejection method...
>
> int rand7()
> {
> int i;
> do
> i = 5 * rand5() + rand5() - 3;
> while( i > 23 );
> return
When you first learned to multiply numbers, you were told that x * y
means adding x a total of y times, so 5 * 4 = 5+5+5+5 = 20. What is
the time complexity of multiplying two n-digit numbers in base b using
the repeated addition method, as a function of n and b. Assume that
single-digit by single-
catalan number works fine
On Sat, Jul 31, 2010 at 4:55 PM, Soumya_Prasad_Ukil
wrote:
> @above,
>result is incorrect for n=4. It should print 14.
>
>
> On 31 July 2010 16:44, Manjunath Manohar wrote:
>
>> the number of unique binary trees which can be formed with n nodes is
>> (2^n)-n
Hi Dave,
i just checked;
int i;
int j;
for(i=1;i<6;i++) {
j = 2*(i/3);
printf("\n%d\n",j);
}
gives me output 0,0,2,2,2. and there was no 3;
and since we are anyway generating "random" numbers would this difference in
distribution really matter?
On Sat, Jul 31, 2010 at 6:30 PM
@Sony. No. Consider the following table:
rand5() (2/3)*rand5()
_
10
21
32
42
53
Thus, (2/3)*rand5() is not uniformly distributed, nor is it in the
range 0 to 2.
Dave
On Jul 31, 7:49 am, S
what about
int i = rand5() + (2/3)*rand5();
won't this work?
On Sat, Jul 31, 2010 at 5:46 PM, Dave wrote:
> Use the rejection method...
>
> int rand7()
> {
>int i;
>do
>i = 5 * rand5() + rand5() - 3;
>while( i > 23 );
>return i / 3;
> }
>
> The loop assigns i a value b
Use the rejection method...
int rand7()
{
int i;
do
i = 5 * rand5() + rand5() - 3;
while( i > 23 );
return i / 3;
}
The loop assigns i a value between 5*1+1-3 = 3 and 5*5+5-3 = 27 with
uniform probability, and then rejects any value of i > 23. Thus, after
the loop, i has a
@above,
result is incorrect for n=4. It should print 14.
On 31 July 2010 16:44, Manjunath Manohar wrote:
> the number of unique binary trees which can be formed with n nodes is
> (2^n)-n
>
> --
> You received this message because you are subscribed to the Google Groups
> "Algorithm Ge
the number of unique binary trees which can be formed with n nodes is
(2^n)-n
--
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
algo
given a rand5 function which generates numbers from 1 to 5 with equal
probability.. give an algorithm which uses rand5 function and generates
numbers from 1 to 7 with equal probability
--
With Regards,
Jalaj Jaiswal
+919026283397
B.TECH IT
IIIT ALLAHABAD
--
You received this message because you
put all the players in a stack
now pop two players from stack
insert the winning player in to a circular doubly linked list.
now repeat the procedure and while inserting in doubly linked list if the
linked list is not null then start from tail and compare the popped node
with it that whether it won
A small correction.
You need to prove if f(n) = O(g(n)).
My Proff (under Note) is for f(n) = Ω(g(n))
On Sat, Jul 31, 2010 at 12:08 AM, sourav wrote:
> f(n) = sqrt(n) [squate root of n]
> g(n) = log(^2) [log of (n square)]
>
> For the above pair of functions is f(n) = Ω(g(n))? i.e., is there som
f(n) = sqrt(n) [squate root of n]
g(n) = log(^2) [log of (n square)]
For the above pair of functions is f(n) = Ω(g(n))? i.e., is there some
c > 0, such that f(n) >= g(n) for all n? Give proof in case answer is
yes or no.
-
int countTree(int num)
{
if(num <= 1) return 1;
int sum =0;
for(i =1; i wrote:
> Follow up on Catalon Nubmer...
>
> On Fri, Jul 30, 2010 at 10:44 AM, Amit Jaspal wrote:
>
>
>
> > n is clearly a number lets say 3 then BST's with 1,2,3 values as key are to
> > be calculated
>
> > On Fri, Jul
is n not the number of nodes?
On Fri, Jul 30, 2010 at 11:58 AM, Pramod Negi wrote:
> Follow up on Catalon Nubmer...
>
>
>
> On Fri, Jul 30, 2010 at 10:44 AM, Amit Jaspal wrote:
>
>> n is clearly a number lets say 3 then BST's with 1,2,3 values as key are
>> to be calculated
>>
>>
>> On Fri, Jul
@Anand, you are partly correct, thanks for modifying my code
On 31 July 2010 00:01, Anand wrote:
> I highlighted the code which I feel need a change. Do let me know if it
> correct.
>
> LinkNode *levelOrderTraversal(node *root, int level)
> {
> LinkNode *ptr1, *ptr2, temp;
>
> if(root == NUL
The question is to find the no of structures possible for a BST which is
directly given bycomputing the catalan number for n(no of nodes)
--
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" group.
To post to this group, send email to algoge...@googlegro
int num_of_BST(int n)
{
int sum=0;
int left,right,root;
if(n<=1)
return 1;
else
{
for(root=1;root<=n;root++)
{
left=num_of_BST(root-1);
right=num_of_BST(n-root);
sum+=left*right;
}
}
return sum;
}
On Thu, Jul 29, 2010 at 9:56 PM, amit wrote:
> Given the numbers from 1 to n, write an algorithm to
Consider there are N players who have a round robin tournament.
input is a data structure which says who won the match for every pair i != j .
write an algo to give a sequence A[1...n] such that for ever i , i th player
lost to i+1 th player and won against i-1 th player.
--
Regards,
Ramkumar.G
can u give example?
is it like that for 3 , a no which is made of 1st ,2nd and 3rd digit
should be divisible by 3 or individual all three digits
must be divisible by 3?
A 2nd case seems impossible.
On Jul 30, 9:12 am, "Shiv ..." wrote:
> If space is not a restriction-
>
> Build a B-tree.
> 1.
39 matches
Mail list logo
