Last Updated: 13 Mar, 2021
Number of squareful arrays
Hard
Asked in companies
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
Approaches
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:-
- 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.
- 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’.
Make a graph where an edge exit from i to j if ARR[i]+ARR[j] is a perfect square. After that count all possible Hamiltonian paths. Total hamiltonian paths will be the number of permutations that are squareful.
Hamiltonian path is a graph path between two vertices of a graph such that all visit all the vertices of the graph at least once.
We will construct the graph where an edge between ‘i’ and ‘j’ if ARR[i] + ARR[j] is a perfect square. We can use dynamic programming to check the hamiltonian paths.
Algorithm:-
- We will first ignore the repetitions and only consider the index permutations.F[S,i] represents the number of permutations when ‘S’ contains the number we had used already, ARR[i] is the last number.
- ‘S’ is a binary number where each bit represents where ‘i’ exits or not.
- Initially F[1<<i, i]=1. Other states are 0.
- Then we will enumerate ‘j’ at each time.
- If ‘j’ is not is ‘S’ and ARR[i]+ARR[j] is perfect square then,
- F[S|1<<j, j] += F[S,i]
- If ‘j’ is not is ‘S’ and ARR[i]+ARR[j] is perfect square then,
- Intialise an int ‘ANS’ = 0,
- Iterate on ‘i’ from 0 to ‘N’, where ‘N’ is size of ‘ARR’.
- Then , ‘ANS’ += F[(1<<N) - 1, i]
- We need to count repeated elements only one , so divide ‘ANS’ from factorial of count of each number in ‘ARR’.
Similar problems