New update is available. Click here to update.

Number of squareful arrays

Posted: 13 Mar, 2021
Difficulty: Hard


Try Problem

You are given an Array/List Arr of non-negative integers. Your task is to return the number of Squareful permutations of the array.

An array is called Squareful if the sum of every pair of adjacent elements is a perfect square.


ARR[1,3,6] is a Squareful array as 1+3=4 i.e. 2^2 , 3+6=9 i.e. 3^2.

Two permutations ARR1 and ARR2, are different from each other if there exit an index i such that ARR1[i] != ARR2[i].


[1,6,3] and [6,1,3] are different permutations.
Input format
The first line contains an integer ‘N’, representing the array’s size.

The second contains 'N' space-separated integers, denoting the elements of the array.
Output format
For each test case, return an integer denoting the number of Squareful Permutation of array ARR.
You don’t need to print anything or take input; it already has been taken care of. Just implement the function.
1 <= N <= 12
0 <= ARR[i] <= 10^4 , where 0 <= i < N

Time limit: 1 sec