PowersOfTwo | Topcoder Archive

Problem Statement

Fox Ciel likes powers of two. She has a bag with some positive powers of two. Note that some powers may occur multiple times in the bag. You are given a long[] powers. Each element of powers is one of the numbers in Ciel's bag.

Ciel likes each non-negative integer that can be written as the sum of some numbers from her bag.

For example, suppose that her bag contains the numbers 2, 4, 4, and 64. In this case, Ciel likes 10 (because 10=2+4+4), 64 (because 64=64), and also 0 (the sum of no numbers). She does not like 1, and she does not like 12 (note that 12=4+4+4 is not valid, as she only has two 4s; 12=4+4+2+2 is also not valid, as she only has one 2).

Return the number of integers Ciel likes.

Definition

Class:: PowersOfTwo
Method:: count
Parameters:: long[]
Returns:: long
Method signature:: long count(long[] powers)
(be sure your method is public)

Constraints

powers will contain between 1 and 50 elements, inclusive.
Each element of powers is a power of two between 1 and 2^50, inclusive.

Examples

```
{1,2}
```
```
Returns: 4
```
Fox Ciel likes 0, 1, 2 and 3.
```
{1,1,1,1}
```
```
Returns: 5
```
Fox Ciel likes 0, 1, 2, 3 and 4.
```
{1,2,2,2,4,4,16}
```
```
Returns: 32
```
```
{1,32,1,16,32}
```
```
Returns: 18
```

{1048576,1073741824,549755813888,70368744177664,4398046511104,262144,1048576,2097152,8796093022208,
 1048576,1048576,35184372088832,2097152,256,256,256,262144,1048576,1048576,70368744177664,262144,1048576}

Returns: 18432

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.