AvoidingProduct | Topcoder Archive

Problem Statement

You are given a set A of integers and a positive integer n. You must find positive integers x, y and z such that their product is as close to n as possible (minimize |n - x * y * z|), and none of them belongs to A. If there are several such triples, find the one with the smallest x. If there are still several such triples, minimize y. If there is still a tie, minimize z.

You are given the elements of A as a int[] a. Return a int[] with exactly three elements: x, y and z, in this order.

Definition

Class:: AvoidingProduct
Method:: getTriple
Parameters:: int[], int
Returns:: int[]
Method signature:: int[] getTriple(int[] a, int n)
(be sure your method is public)

Constraints

a will contain between 0 and 50 elements, inclusive.
Each element of a will be between 1 and 1000, inclusive.
All elements of a will be distinct.
n will be between 1 and 1000, inclusive.

Examples

```
{2,4}
```
```
4
```
```
Returns: {1, 1, 3 }
```
You can get 3=1*1*3 and 5=1*1*5. 3 is better.
```
{1}
```
```
10
```
```
Returns: {2, 2, 2 }
```
```
{1,2}
```
```
10
```
```
Returns: {3, 3, 3 }
```
```
{1,3}
```
```
12
```
```
Returns: {2, 2, 2 }
```
```
{1,3}
```
```
13
```
```
Returns: {2, 2, 4 }
```
```
{1,15}
```
```
90
```
```
Returns: {2, 5, 9 }
```

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.