Changing binary counter structure such that increament and decreament methods will work in O(1) amortized Just trying to solve the second part of a question with two parts.
First part was to prove that you can't add decrement method to a standart binary counter without hurting the amortized complexity and change it to be more than O(1).
This part i have done with no problems.
Solution in a nutshell - after some method you are going to be in a dead end when you have a number like this: 100...0 so when you decrease by 1 you will get 0111...1 and then when you will increase by 1 you will get again 100...0 and those decreasment and increament are cost n and you will do them m times so its not O(1) amortized.
The second part, is to tell how you can change the structure such that it will support decreament and increase methods and the amortized complexity will stay O(1).
I never saw something like this and it really confusing me what they want me to do.
Their solution is that anytime you want to change 0 to 1 you change it to minus 1.
Problem is, i can't understand what they meant, i mean, on which stracture you are inserting this change and how does it improved the complexity (if you change to -1 you stil going to the same dead end).
They may by suggesting that you use a binary counter with three digit values, $\{-1,0,1\}$, and budget a fixed additional time whenever you set a digit to $\pm1$.
To increment the counter you start at the least significant trit, and if it's $-1$ you set it to $0$ and stop, if it's $0$ you set it to $1$ and stop, and if it's $1$ you set it to $0$ and loop (using the previously budgeted time). Decrementing is the same with everything negated.