Given a array, find the n increasing number whose summation will be maximum.

Thanks to my friend pallav for asking this.

Certainly its DP, I will post once i am through.

## Thursday, February 25, 2010

## Friday, February 5, 2010

### [Tree]..Is parent or grandparent?

There are two nodes given in a tree(not binary tree). Find whether one node

is parent/grand parent of other.

order should be O(1).

tag root as 0 , tag left child as 00 , right child as 01.

left child's left child as 000 , left's child's right child as

001 ... and so on.

now

let input be tags t1 and t2

if( (t1 == (t2>>1)) || (t2==(t1>>1)))

return child parent relationship

if( (t1 == (t2>>2)) || (t2==(t1>>2)))

return child grand-parent relationship ...

This solution can take a lot of space as the three grows.

We can tag the node by number ..

Root -0

1 -2-3-4

SO given two node get their tags..

Get Max of both t1, t2.

Go for parent of that node if other node then return or check for parent of parent and check again for other node.

With 2^32 value avaialable for indexing ..u wont run out of values.

is parent/grand parent of other.

order should be O(1).

tag root as 0 , tag left child as 00 , right child as 01.

left child's left child as 000 , left's child's right child as

001 ... and so on.

now

let input be tags t1 and t2

if( (t1 == (t2>>1)) || (t2==(t1>>1)))

return child parent relationship

if( (t1 == (t2>>2)) || (t2==(t1>>2)))

return child grand-parent relationship ...

This solution can take a lot of space as the three grows.

We can tag the node by number ..

Root -0

1 -2-3-4

SO given two node get their tags..

Get Max of both t1, t2.

Go for parent of that node if other node then return or check for parent of parent and check again for other node.

With 2^32 value avaialable for indexing ..u wont run out of values.

## Thursday, February 4, 2010

### Printing Real number Problem

Given an integer say i of size 32.

Now if i mention a fixed point say 12.

We have to convert/treat above integer to a real number.

So From bit 12....31 will form integer part.

and from 0...11 will be after decimal part.

Now the problem is that we have to print this as real value

without any floating point operation and division operation.

My friend, provided this solution.

for bit 11 -> 5^1 * 10^11 = 500000000000

for bit 10 -> 5^2 * 10^10 = 250000000000

----------

--------

for bit 0 -> 5^11 * 10^0 = ...............(calculate the value)

Add all the above value and print as decimal but after a . char.

Now if i mention a fixed point say 12.

We have to convert/treat above integer to a real number.

So From bit 12....31 will form integer part.

and from 0...11 will be after decimal part.

Now the problem is that we have to print this as real value

without any floating point operation and division operation.

My friend, provided this solution.

for bit 11 -> 5^1 * 10^11 = 500000000000

for bit 10 -> 5^2 * 10^10 = 250000000000

----------

--------

for bit 0 -> 5^11 * 10^0 = ...............(calculate the value)

Add all the above value and print as decimal but after a . char.

Subscribe to:
Posts (Atom)