×

Setter: Misha Chorniy
Editorialist: Taranpreet Singh

Easy-Medium

# PREREQUISITES:

Bitwise operation, Dynammic Programming.

# PROBLEM:

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$.

# EXPLANATION

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.

View Content

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.

View Content

Editorialist's talk

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

# Time Complexity

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. :)

This question is marked "community wiki".

3.6k1863
accept rate: 23%

19.6k349497539

Almost similar problem A. XOR Equation.

(29 Oct, 03:38)

 0 answered 21 Oct, 23:37 16●2 accept rate: 20% I couldn't understand your code (28 Oct, 13:23) vjvjain04★
 2 Thank you for your highly insightful editorials! I remembered your editorials from ICO prep round and previous contests which helped me improve my dp. Because of it I was able to solve this question. Please keep posting these lovely editorials. ;) answered 21 Oct, 19:54 41●1 accept rate: 0% Again... XD (21 Oct, 19:58) Fun Fact - @l_returns is the first person to comment on this answer. Mega Fun Fact - @tarini_1407 and @taran_1407 study in same college. So @taran_1407 you have got one teammate. Search reduced to finding one more. xD (21 Oct, 20:04) Fun fact 3 - This statement is worth reading. https://www.codechef.com/ICOP1902/problems/TARITAR I guess @taran_1407 has a huge female fan following in his college (21 Oct, 20:08) I expect one of my friends is pulling this prank on me. As far as I know, There is no Tarini in my college. So, teammate search continues. (21 Oct, 20:11) 1 @vijju123 and @aryanc403 XDD (21 Oct, 20:13) lol. Someone using his powers. View Content View Content (21 Oct, 20:39) 1 Thats because it will spam the editorial. 1-2 jokes are fine but that answer simply opens up a new road to spam more and more XD. I dont have issues of it using my name, but the fact that it will spam the editorial unnecessarily - I consulted taran also before removing it. (21 Oct, 20:48) Hi @vijju123, Please don't disappoint me and you can convert my answers into a comment on @tarini_1407 answers. Sadly, I don't have powers to do so. :( (21 Oct, 21:09) There is no Tarini in my college. lol. You have searched your college database? (21 Oct, 21:11) XDDDDDDDDD (21 Oct, 21:14) @aryanc403 - @taran_1407 knows everything about girls in his college, as evident from his statement ;) @vijjji123 - Sadly there, there is only disappointment from me in your fate. I wont be writing editorials for a long, long time XD. (21 Oct, 21:26) @ everyone I just hope next time you all will read my comment carefully. I explicitly mentioned "As far as I know" xD (21 Oct, 23:24) Please dont make fun of me or taran! (27 Oct, 23:38) showing 5 of 13 show all
 2 Problem in Practice Section is not visible. answered 21 Oct, 21:57 497●1●8 accept rate: 15%
 0 Awesome Editorial just loved it :) learnt something new answered 22 Oct, 13:47 1 accept rate: 0% Glad you found it useful. (24 Oct, 16:37)
 0 Hey, For the test case 369 428 797, can you please explain why pairs like (1,796), (2,795) ... (795,2) (796,1) valid? After all, they are obtained by shuffling some bits in A and B. Can you please point out where I am getting confused? Thanks answered 22 Oct, 18:19 2★chari407 447●2●7 accept rate: 0% All of these pairs are not valid. For verification, write a brute program which iterates over all pairs of (i, c-i) and count the number pairs in which i have same bit count as a and (c-i) has the same bit count as B. (22 Oct, 20:25)
 0 "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≠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." @taran_1407 @vijju123 can you please explain these bunch of statements with an example. answered 23 Oct, 18:14 3★kunal12 44●5 accept rate: 0% Add two numbers in binary form. 1010 0110 you'll see, that sum is 10000. This happened due to carry forward at bit index 1, 2 and 3 (counting from least significant to most significant). Analyse this example and you'll get it. (24 Oct, 16:40) can you please give one more example explaining this x, cf and y. (24 Oct, 16:45) kunal123★ Other examples would be similar. I recommend you read and Binary Arithmetic (specifically Binary addition), which you may find by googling. (24 Oct, 16:54)
 0 tester solution This solution is showing runtime error(sigtstp) I think its because of declaring such big array. Its having time complexity of O(10^9). answered 24 Oct, 18:03 4★mohit96m 76●2 accept rate: 16%
 0 What is the brute force approach that would solve one sub task? answered 25 Oct, 22:10 11●1 accept rate: 0%
 0 @taran_1407 In recursive function, if we add an extra condition bit_a==0 && bit_b==0 return 0; produces WA. Can anyone explain the reason? answered 27 Oct, 23:28 35●6 accept rate: 0% I did not get what you want to say. (27 Oct, 23:55) In your solution, if we add an extra condition in recursive function ans a == 0&& b== 0 return 0 gives WA. Why ? and why do we need to add condition bit==B ?? (28 Oct, 09:23) 1 Because cf may be balancing the remaining bits as required for c. Like, suppose we have a==0 && b==0. we need the current bit to be 1, and cf is also 1. Hence, This bit we get from cf. Assuming all next bits are 0, we have one way which, due to that condition, will be missed. (28 Oct, 14:32) @taran_1407 Thanks :) (31 Oct, 13:35)
 0 tester program give time limit exceed @admin answered 28 Oct, 20:52 1 accept rate: 0%
 toggle preview community wiki:
Preview

By Email:

Markdown Basics

• *italic* or _italic_
• **bold** or __bold__
• image?![alt text](/path/img.jpg "title")
• numbered list: 1. Foo 2. Bar
• to add a line break simply add two spaces to where you would like the new line to be.
• basic HTML tags are also supported
• mathemetical formulas in Latex between \$ symbol

Question tags:

×1,952
×1,602
×446
×182
×36
×11