FoxAndKgram | Topcoder Archive

Problem Statement

Fox Ciel has some pencils. Before she'll start writing her homework, she wants to place them into a mystic pattern for fun. Different pencils she has may have different lengths. You are given a int[] len. For each i, the length of i-th pencil is len[i]

The pattern she wants to create is called a k-gram. A k-gram is a pattern consisting of k rows, each of length k. There are only two types of valid rows:

Yang: A row containing a single pencil of length k.
Yin: A row containing two pencils such that the sum of their lengths is (k-1). The pencils will be separated by a space of length 1.

Compute and return the largest positive integer k such that Fox Ciel can use some of her pencils to form a k-gram. If she is unable to form any k-grams, return 0 instead.

Definition

Class:: FoxAndKgram
Method:: maxK
Parameters:: int[]
Returns:: int
Method signature:: int maxK(int[] len)
(be sure your method is public)

Constraints

len will contain between 1 and 50 elements, inclusive.
Each element in len will be between 1 and 50, inclusive.

Examples

```
{1,1,1,1,3}
```
```
Returns: 3
```
All pencils can be used to form a 3-gram. One valid 3-gram follows: - - --- - -
```
{2,2,1,3,5,5,5}
```
```
Returns: 5
```
One of the valid 5-grams: ----- -- -- - --- ----- -----
```
{1}
```
```
Returns: 1
```
```
{2,2,2,2,2,2,2,2,2,2}
```
```
Returns: 5
```
```
{1,2,3,1,2,4,2,3,1}
```
```
Returns: 4
```
Note that it is not necessary to use all of the pencils.
```
{2,3,5,7,11,13,17,19,23,29}
```
```
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.