Avoid9 | Topcoder Archive

Problem Statement

A set of integers is called 9-free if it has the following properties:

It contains at least three elements.
For every three distinct elements x, y, z in the set, the value (x+y+z) is not divisible by 9.

You are given a int[] A containing a set of distinct integers. Return the size of the largest subset of A that is 9-free. If there is no such subset, return -1 instead.

Definition

Class:: Avoid9
Method:: maxSizeOf9Free
Parameters:: int[]
Returns:: int
Method signature:: int maxSizeOf9Free(int[] A)
(be sure your method is public)

Constraints

A will contain between 3 and 200 integers, inclusive.
Each element of A will be between 0 and 1,000,000, inclusive.
All the elements of A will be distinct.

Examples

```
{6, 9, 5, 3}
```
```
Returns: 3
```
The whole four-element set A is not 9-free, because (6+9+3) is divisible by 9. The subset {9, 5, 3} is 9-free, because (9+5+3) is not divisible by 9. Thus, the size of the largest 9-free subset of A is 3.
```
{6, 9, 18, 3, 15, 12}
```
```
Returns: 4
```
Subset {6, 3, 15, 12} is 9-free. It is easy to verify that no larger subset of A is 9-free.

{1, 10, 7, 19, 16, 28, 9, 46, 0, 37}

Returns: 8

```
{3, 12, 30, 6, 21, 4, 15, 9}
```
```
Returns: 5
```

{600308, 404694, 939932, 748673, 891293, 706905, 978182, 625631, 708003, 977632, 828206, 972547, 
184606, 929681, 237869, 610370, 559760, 939323, 272684, 162248, 168143, 753163, 302535, 153367, 
568583, 750868, 735416, 97724, 620300, 509987, 129310, 993312, 323413, 676205, 629534, 894380, 1791, 
499727, 751959, 456281}

Returns: 23

```
{12, 93, 48}
```
```
Returns: -1
```

{993320, 112864, 892808, 821699, 227492, 901628, 467512, 142654, 810125}

Returns: 9

The whole set A can also be the desired 9-free subset.

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.