New update is available. Click here to update.

Number of squareful arrays

Posted: 13 Mar, 2021
Difficulty: Hard

PROBLEM STATEMENT

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.

Example

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].

Example:

[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.
Note:
You don’t need to print anything or take input; it already has been taken care of. Just implement the function.
Constraints:-
1 <= N <= 12
0 <= ARR[i] <= 10^4 , where 0 <= i < N

Time limit: 1 sec