anm_coder007's blog

By anm_coder007, history, 5 years ago, In English

A Prime Array is an array which doesn't contain a pair of numbers whose product is a square of an integer.

For eg [1,2,3] is a Prime Array but [1,2,4] is not.

Explanation : 1*4 gives 4 which is square of 2.

Given an array of integers determine the minimum number of operations to convert the array to a Prime array.

NOTE: An operation consists of either increasing or decreasing any element of the array by 1 but the element should always be positive.

Constraints: Length of array <=100

1 <=Each integer in array <=1000000

Eg. Array => [1,1,2]

Minimum operations to convert [1,1,2] to [1,2,3] is 2.

  • Vote: I like it
  • 0
  • Vote: I do not like it

| Write comment?
»
5 years ago, # |
Rev. 18   Vote: I like it 0 Vote: I do not like it

The problem can be formulated as follows.

Given an integer array A = [a1, a2, ..., an], where 1 ≤ n ≤ 100, and 1 ≤ ai ≤ 106, find an integer array D = [d1, d2, ..., dn] such that:

  1. di >  - ai for all 1 ≤ i ≤ n

  2. The array B = A + D, where bi = ai + di, is Prime, and

  3. The objective function is minimized.

The following are few hints that may be helpful in solving the problem:

  1. An array B with n = 1 is Prime for any value of its element.

  2. A Prime array B with n > 1 should have distinct elements.

  3. A Prime array B with n > 1 should have at most one element that is a square of an integer.

  4. A Prime array B with n > 1 should have distinct odd-power prime factors for each element. For example, an array that contains 150 and 294 in not Prime, because both elements have the same odd-power prime factors 2 and 3, 150 = 2 x 3 x 5 x 5 and 294 = 2 x 3 x 7 x 7, and their multiplication 150 x 294 = 44100 is guaranteed to be square. In this example, 44100 = 210 x 210 and 210 = 2 x 3 x 5 x 7. Note that any square of an integer should have no odd-power prime factors, as all powers of its prime factors should be even numbers.

  5. The answer does not depend on the order of the elements in the array. Therefore, sorting the array when n > 1 may be a good approach to reduce the computational complexity of the solution.

P.S. Just a kind reminder to what several members of the Codeforces Community indicated before: a link to the problem statement should be provided in the blog if possible, and the problem should not be presently in a running contest.