/sci/ - Science & Math

[Anonymous No.9184628]

>Dynamic programming task
I am not really good at handling dynamic programming problems(brainlet).

Given integers [math]a, b, c \ (1 \leq a, b, c \leq 2^{30})[/math] I have to rearrange digits of their binary notation to get the following relation: [math]a' + b' = c'[/math] and this [math]c'[/math] has to be smallest possible, the output is [math]c'[/math]. In other words, the program has to output the smallest integer with exactly [math]k[/math] 1-bits in its binary notation that is the sum of two integers with exactly [math]m, l[/math] 1-bits in their binary notations respectively. For example, given [math]a = 4, b = 8, c = 3[/math] (two numbers with only one 1-bit and one with two 1-bits) the answer is [math]3[/math] as [math]1 + 2 =
3[/math] (still the same number of 1-bits as in original numbers). Of course such an integer may not exist.

This problem is supposed to be DP one but I don't even see what is the subproblem in this case so there is no chance I come up with DP relation with my current understanding of a problem. The only thing that comes to my mind is that this problem may involve an array of length [math]32[\math](for each bit).

Please help a brainlet...