SquareFreeSet | Topcoder Archive

Problem Statement

Andrew has an array of positive integers. You are given the array in the int[] x.

Andrew calls an array of positive integers square-free if it has the following property: for each pair of distinct indices i, j the product x[i] * x[j] is not a perfect square.

For example, {4, 5, 6} is a square-free array because the numbers 4*5, 4*6, and 5*6 are not perfect squares. (Note that an individual element of the array, such as 4 in our example, may be a perfect square.)

The array {2, 47, 50} is not square-free because 2*50 = 100 is a perfect square.

The array {5, 7} is square-free but the array {5, 7, 7} is not square-free because 7*7 = 49 is a perfect square.

Andrew would like to change x into a square-free array. He can pay 1 to increase or decrease any single element of x by 1. He can modify the same element multiple times, the only restriction is that at the end all elements of x must still be positive integers.

Find and return the minimum total cost of changing x into a square-free array.

Definition

Class:: SquareFreeSet
Method:: findCost
Parameters:: int[]
Returns:: int
Method signature:: int findCost(int[] x)
(be sure your method is public)

Notes

An integer is called a perfect square if it can be written as k*k for some integer k.

Constraints

x will have between 1 and 100 elements, inclusive.
Each element of x will be between 1 and 10^6, inclusive.

Examples

```
{1,2,1,2}
```
```
Returns: 5
```
One optimal solution is to change this array into {3,2,1,5}. This costs 5, as we have to increment element 0 twice and element 3 three times. The array {3,2,1,5} is square-free. The six possible pairwise products are 3*2=6, 3*1=3, 3*5=15, 2*1=2, 2*5=10, and 1*5=5. The values 6, 3, 15, 2, 10, and 5 are not perfect squares.
```
{7,7,7}
```
```
Returns: 2
```
One optimal solution is to change this array into {6,7,8}.
```
{4,5,6,47}
```
```
Returns: 0
```
This is a square-free array, no changes necessary.
```
{1,10,1,1,1,1,10}
```
```
Returns: 13
```

{4,5,6,7,8,9,10,11,12,13,14,15,16,17,1,1,1,1,1,1,1,1,1,1,1,1,1,1}

Returns: 443

```
{1000000}
```
```
Returns: 0
```

{9450,7098,6048,1050,672,8232,5028,
672,672,42,42,42,42,42,9450,6048,
3402,3402,2688,9450,7098,6048,1050,
672,8232,5028,672,672,9450,6048,3402}

Returns: 42

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.