BinarySum | Topcoder Archive

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 ints a, b and c. Return the minimal possible value of c'. If there is no solution, return -1.

Definition

Class:: BinarySum
Method:: rearrange
Parameters:: int, int, int
Returns:: int
Method signature:: int rearrange(int a, int b, int c)
(be sure your method is public)

Constraints

a, b and c will each be between 1 and 2^30, inclusive.

Examples

```
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
```
```
1
```
```
1
```
```
1
```
```
Returns: -1
```
```
32517565
```
```
204650420
```
```
4096
```
```
Returns: -1
```

This problem statement is the exclusive and proprietary property of Topcoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of Topcoder, Inc. is strictly prohibited. (c)2024, Topcoder, Inc. All rights reserved.