BinarySum
SRM 399 · 2008-04-24 · by andrewzta
Problem Statement
You are given three integers: a, b and c. Convert each of them into their binary representations with no leading zeroes. Let x be the number of binary digits in the longest of the three. Add leading zeroes to the others until all of them have exactly x digits.
Transform a, b and c into a', b' and c', such that a'+b'=c', by optionally reordering the digits within each number. Leading zeroes are allowed. If there are several ways to do this, use the one that minimizes c'.
For example, let a = 7, b = 6 and c = 9. In binary notation, a = 111, b = 110 and c = 1001. We add leading zeroes to a and b so that all of them have exactly four digits: a = 0111, b = 0110, c = 1001. Now, if we reorder the digits within each number to get a' = 0111, b' = 0011 and c' = 1010, we satisfy a' + b' = c' (7 + 3 = 10). There is another way to do this as well (7 + 5 = 12), but this is the way that minimizes c'.
You are given
Constraints
- a, b and c will each be between 1 and 2^30, inclusive.
7 6 9 Returns: 10
The example from the problem statement.
1 1 2 Returns: 2
1 1 4 Returns: 2
Leading zeroes are allowed.
3 3 9 Returns: 6
334308079 476771809 343926580 Returns: 524285
Submissions are judged against all 116 archived test cases, of which 5 are shown here. Case numbers match the judge’s.
Language: C++17 · define a public class BinarySum with a public method int rearrange(int a, int b, int c) · 116 test cases · 2 s / 256 MB per case