WinterAndCandies | Topcoder Archive

Problem Statement

It's winter time! You have some candies arranged in a row and now you want to choose some of them and give them to your friend.

You are given a int[] type. Each candy has a type, which is some positive integer. For each i, type[i] represents the type of i-th candy. You want to choose some non-empty subset of candies with the following property: if the number of candies you choose is K, their types must be precisely all the numbers from 1 to K, inclusive. Return the number of different ways to do that. (Two ways are considered different if there exists some candy that is chosen in only one of them.)

Definition

Class:: WinterAndCandies
Method:: getNumber
Parameters:: int[]
Returns:: int
Method signature:: int getNumber(int[] type)
(be sure your method is public)

Notes

The answer will always fit in a signed 32-bit integer.

Constraints

type will contain between 1 and 50 elements, inclusive.
Each element of type will be between 1 and 50, inclusive.

Examples

```
{1, 3, 2}
```
```
Returns: 3
```
There are 7 possible non-empty subsets in this case: (1) (3) (2) (1, 3) (1, 2) (3, 2) (1, 3, 2) Out of them, only first, fifth and seventh are valid. Thus, the answer is 3.
```
{1, 1, 2}
```
```
Returns: 4
```
Note that the chosen subset can never contain two elements with the same type.
```
{1, 3, 2, 5, 7, 4, 5, 4}
```
```
Returns: 9
```

{1, 1, 2, 2, 3, 3, 4, 4, 5, 5}

Returns: 62

```
{2}
```
```
Returns: 0
```

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.