Markus
BAN USERand moreover as 3*9-1*(20+6) = 1 (either see it or use extended euclidean algorithm)
you can start with
6*(20+6) = 156
6*(20+6) + 3*9 - 1*(20+6) = 157
6*(20+6) + 6*9 - 2*(20+6) = 158
6*(20+6) + 9*9 - 3*(20+6) = 159
6*(20+6) + 12*9 - 4*(20+6) = 160
6*(20+6) + 15*9 - 5*(20+6) = 161
and obviously all other sizes will be also possible as 156+6=162, 157+6=163 and so on
so you only need to calculate solutions untill 156 at most!
Theoretically any problem which can be written iteratively can also be written recursively"
I highly doubt that!
The idea of the recursive tree traversal is that your node stack that you need in an iterative solution is implicitly handled by recursive calls, you put a node on the stack by calling the function again, you pop a node by returning to the calling function.
If you try to handle both trees in the same function you'll come to a point where one tree wants to pop an element from the stack in the iterative solution and the other wants to put yet another element on top of the stack.
Thus in the recursive solution for one tree you have to return from your function and for the other tree you have to make another recursive call! That's not possible.
That's pure coincidence ;)
You have to sort the given elements in a way, that for every element e, there are "NumberOfTall" elements in front of e, that have a greater "height" value.
For example there has to be one element in front of D that is taller and that element would be F. In fact there's always only one possible solution, if all heights differ. In the given example coincidentally the reverse order ;)
Great solution. There might be a small error though:
After popping an element from the stack in maxHistRect you calculate the max area as
histogram[cur]*(i-cur)
histogram[cur] is obviously the height, i the right border, and cur the left border of the rectangle. The left border can be more on the left side. In fact the left border is the index of the top element on the stack after popping, thus it should be:
histogram[cur]*(i-stack.top())
nice but wrong... at least you're on the right track
- Markus March 08, 2014one remaining problem:
N = 12345
In the first iteration your are right that every digit has to appear 1234 times in the right most place.
In the second iteration N = 1234, now every digit in the right most place has to appear 123 times according to your logic, but as there is a degree of freedom it has to apper 123 times * 10
In the next step N = 123, every digit has to apper 12 times but is supported by two degrees of freedom -> 12*100