BadBinary | Topcoder Archive

Problem Statement

Given a positive integer k, the binary representation expresses k as a sum of powers of 2. Each digit in the binary representation is allowed to be 0 or 1 (for example, 9 = 1001₂ = 2³ + 2⁰). What if it could be 0, 1 or 2? Given k you will return how many different binary decompositions it has, where the digit values can be 0, 1 or 2. Note, each representation has no leading zeros.

Definition

Class:: BadBinary
Method:: howMany
Parameters:: int
Returns:: long
Method signature:: long howMany(int k)
(be sure your method is public)

Constraints

k will be between 1 and 2^31-1, inclusive.
The return value will be at most 2^63-1.

Examples

```
1
```
```
Returns: 1
```
"1" is the only answer.
```
2
```
```
Returns: 2
```
Two possibilities are "10" and "2".
```
3
```
```
Returns: 1
```
"11" is the only answer.
```
4
```
```
Returns: 3
```
"100", "20" and "12".
```
10
```
```
Returns: 5
```
"1010", "1002", "210", "202" and "122".
```
489225632
```
```
Returns: 67366
```

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.