Hello Codeforces, Recently I gave an interview exam of software company and they asked one question that stumped me. The question goes as follows:
An array Arr of size n is called Prime Array if there exists at least one pair {i,j}(i≠j and 0<=(i,j)<n), such that Arr[i]*Arr[j] is a perfect square number.
You are given an array a, you are allowed to perform following operation on its elements any number of time:
[Pick an index i(0<=i<n), set a[i]=a[i]+1 or a[i]=a[i]-1].
Your task is to find minimum operations required to convert array a into a Prime Array.
Constraints:
1<=n<=100
1<=a[i]<=10^8
Input:
The first line contains an integer n, the size of the array a.
The second line contains n integers, the elements of array a.
Example:
Input:
3
7 7 7
Output:
2
Explanation:
By updating a[1]=a[1]+1 and a[2]=a[2]-1 we can make the array Prime Array (a={7,8,6}) in 2 operations.
I am really struggling to solve this question but not able to solve it. So finally after nearly a weak of effort, I am asking from the Codeforces Community. Any response would be highly appreciated.