3 ms·
Yes, the original auxiliary array has to start out being zero, but it is returned in that same state, so this algo can be run over and over again without ever h
by daniel-cussen 7y ago
Yes, the original auxiliary array has to start out being zero, but it is returned in that same state, so this algo can be run over and over again without ever having to reinitialize the entire array in O(2^k).
When there's 2^n and 2^(n+1)-1, it takes n-2 steps to reach the former from the latter, not 2^n.
- Veedrac 7y agoOK, I got it after reading the code. It's a neat trick, but you never actually explain how it works (even the comment says ‘this part I'm confused about’ lol).
- daniel-cussen 7y agoI think I know what you mean. There is a step in the logic that, in a staircase metaphor, is uneven, it's a larger gap than the other steps, and also like a real staircase, you either make that step or you don't. I have yet to find a way to explain it. Personally, I can't always understand it, and don't know how I know it, and can't put my finger on what the leap is.