 # Doubt in Problem-Sort the Array of Amritapuri Practice Round-6

I have a doubt in problem Sort the array- Link
How is just checking whether the product of the index at which the element is currently placed and the index at which it should be in sorted array is a perfect square, guarantees the solution of the problem. Can someone explain how is this code giving AC?

`````` #include <bits/stdc++.h>
using namespace std;
#define int long long
bool isPerfectSquare(int x)
{
int sq=sqrt(x);
return (x==sq*sq);
}
signed main() {
// your code goes here

int t,n;
cin>>t;
while(t--)
{
cin>>n;
int arr[n];
vector<pair<int,int>> vect;
for(int i=0;i<n;i++)
{
cin>>arr[i];
vect.push_back({arr[i],i+1});
}
bool flag=1;
sort(vect.begin(),vect.end());
for(int i=0;i<n;i++)
{
int x=(i+1)*(vect[i].second);
if(isPerfectSquare(x)==0)
{
flag=0;break;
}
}
if(flag==1)
cout<<"YES"<<endl;
else
cout<<"NO"<<endl;
}
return 0;
}``````
2 Likes

Suppose y*z=k1^2. Then we can derive the following two relations:

• x*y=k2^2

• x*z=k3^2, where x!=y!=z

We can assume x to be the desired index of any element a[y] in the sorted array, and y to be the original index.
Similarly, z would serve as any index such that a[y] can be swapped with a[z]. By above logic, if we can swap a[x] and a[z] (which we would have to do at least once to move it to the correct index), we can swap a[x] and a[y] as well. Therefore checking for x,y to be a perfect square should suffice.

1 Like