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 no 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.
Need some clarification on the question.
can
arr[i]be equal toarr[j], while considering forarr[i]*arr[j]?and in
a=[7,8,6], multiplying which two numbers give a perfect square number?Edit: context: The initial question was whether there exists at least a pair
{i,j}such thatarr[i]*arr[j]is a perfect square. (which was a typo)Question updated (there was slight error due to autocorrect earlier). Yes arr[i] can be equal to arr[j] as it was also given in example.
it's the opposite, there must be no way to create a perfect square in the array . [7,8,6] can't make a perfect square
a prefect square is a number written as $$$x^2$$$
so a rephrasing of the problem is "what the minimum number of operations to remove duplicates in the array "
Sorry, I just realized that 8*2 is a perfect square so my logic isn't correct
The question says
there exists no pair