# Number of squareful arrays

Posted: 13 Mar, 2021
Difficulty: Hard

## PROBLEM STATEMENT

#### Example

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

#### 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
`````` Approach 1

In this approach, we will check all the permutations of the array. And for each permutation in array ‘ARR’, check if ARR[i]+ARR[i+1] is a perfect square. If it is a perfect square, then increase the answer by 1. Return answer.

Algorithm:-

1. Function for checking if a specific permutation of ‘ARR’ is Squareful or not.
• Make a function bool CHECK(vector<int> &ARR)
• Iterate ‘i’ from 0 to length of ‘ARR’.
• If floor(sqrt( ARR[i] + ARR[i+1] ))!=ceil(sqrt(ARR[i] + ARR[i+1])), return false.
• Else return false.
1. Function for counting all Squareful permutation
• Initialize an int ‘COUNT’ = 0;
• Sort the array ‘ARR’ in increasing order.
• Run a do-while loop to check all Squareful permutations.
• do -> if CHECK(ARR) , then increase count.
• While keep checking for the next permutation of ‘ARR’.