CommonFactors | Topcoder Archive

Problem Statement

You are given a list of numbers in a int[] n. A number k is a factor of number m if m can be exactly divided into k. Find the factor greater than 1 that is shared by the most elements in n. If there are several such factors, return the largest one among them.

Definition

Class:: CommonFactors
Method:: mostCommon
Parameters:: int[]
Returns:: int
Method signature:: int mostCommon(int[] n)
(be sure your method is public)

Constraints

n will contain between 1 and 50 elements, inclusive.
Each element of n will be between 2 and 1000000000, inclusive.

Examples

```
{2, 3, 4, 6}
```
```
Returns: 2
```
2 is a factor of 3 elements of n (2, 4 and 6). 3 is a factor of two elements (3 and 6). 4 and 6 are not factors of any numbers except themselves.
```
{2, 3, 6}
```
```
Returns: 3
```
Both 2 and 3 are factors of exactly two numbers. Based on the tie-breaker rule, we pick the larger.
```
{2, 3, 5, 7}
```
```
Returns: 7
```
No factor appears more than once, so again we use the tie-breaker rule.
```
{2, 3, 5, 6, 7, 9, 11, 12}
```
```
Returns: 3
```
```
{24, 12, 37, 18, 11}
```
```
Returns: 6
```
```
{3, 49, 7, 100, 100}
```
```
Returns: 100
```

{123456789, 987654321, 246813579, 975318642}

Returns: 9

{1000000000, 999999999, 999999999}

Returns: 999999999

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.