Bitwise operation, Dynammic Programming.
Given three numbers A, B and C, given A+B = C, We can change positions of bits in A as well as in B. Calculate Number of ways we can do so, such that their sum is C.
SUPER QUICK EXPLANATION
- Solve the problem in increasing order of bits, handling carry forward carefully.
- Dynamic Programming state consists of tuple (bit, cntA, cntB, carry), where bit is the bit position, cntA is number of bits of A not yet used, cntB is number of bits of B not yet used, and carry tells whether we have one carry forward from the previous position or not.
- Final answer is the value of tuple (0, bit(A), bit(B), carry), where bit(X) counts the number of set bits in X.
This solution seems complicated implementation at first sight, but is actually not, if you are comfortable with Bitwise Operations.
First of all, I am going to share very basic stuff about bitwise addition in secret box.
Click to view
Addition of three in Binary
0+0+0 = 00 = 0 value, 0 carry
0+0+1 = 01 = 1 value, 0 carry
0+1+0 = 01 = 1 value, 0 carry
0+1+1 = 10 = 0 value, 1 carry
1+0+0 = 01 = 1 value, 0 carry
1+0+1 = 10 = 0 value, 1 carry
1+1+0 = 10 = 0 value, 1 carry
1+1+1 = 11 = 1 value, 1 carry
This stuff will be useful.
Now, we all know, that we A+B should have all bits same as C. We need to count the number of ways to shuffle bits. So, we are going to handle problem bit-by-bit.
Important thing is, that If we add two bits at a position, there may be a carry forward to next bit. This means, that bit to be chosen at the next significant position is dependent on carry-forward from the previous position. This means, that we have to approach the bits from least significant bit to most significant bit.
So, Suppose we need to have a bit at current position to be x, with carry-forward cf from the previous position.
If x is same as cf, We can either have the current bit set in both numbers or none of them. Because if we choose to have set bit in exactly A or B at the current bit, the current bit will get flipped, resulting in A+B \neq C.
If x is not same as y, we have to flip the current bit, which can be done only if exactly one of the A or B have current bit set, which will lead to flipping the current bit.
If you have understood this much, give it a try.
After doing this much, If you build a simple recursive solution, we would probably get Time Limit Exceeded, since our solution is calculating some values multiple times, resulting in exponential time complexity.
To speed up, you can just notice, that you can build a lookup table ans[bit][cntA][cntB][carry], storing answer for the tuple (bit, cntA, cntB, carry) and instead of calculating it, just look it up from here. This result in reducing time complexity from exponential to polynomial time complexity, sufficiently fast to pass time limit.
A secret box, only for people who do not know Dynamic Programming.
Click to view
You all know Dynamic Programming. You just read what is dynamic programming. In simple words, storing results when calculated once, and reusing them us called Dynamic programming. That’s all. Only thing, which makes Dynamic Programming a scary thing for some people, is identifying, which information to store. This we can learn with practice.
I was going through some accepted codes for this problem when I found this really nice solution. Have a look. I was looking for an iterative solution to this problem. Anyone having completely iterative solution will be mentioned here. Please share with me the link of code.
EDIT: A completely iterative solution can be seen here, by @pulkit_sja
As you will commonly find in dynamic programming problems, Actual time complexity depends upon Number of states visited.
AUTHOR’S AND TESTER’S SOLUTIONS:
Feel free to Share your approach, If it differs. Suggestions are always welcomed.