Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding Ninjas X Naukri.com

Number of squareful arrays

Hard
0/120
Average time to solve is 50m
profile
Contributed by
17 upvotes
Asked in companies
eBayAppleUber

Problem statement

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.
Detailed explanation ( Input/output format, Notes, Images )
Constraints:-
1 <= N <= 12
0 <= ARR[i] <= 10^4 , where 0 <= i < N

Time limit: 1 sec
Sample input 1
3
1 24 3
Sample output 1
2
Sample input explanation
Different permutations of [1, 24, 3] are - [1, 24, 3] , [1, 3, 24] , [24, 1, 3] , [24, 3, 1] , [3, 1, 24] , [3, 24, 1].

Out of which [24, 1, 3] (24 + 1 = 25, 1 + 3 = 4) and [3, 1, 24] (3 + 1 = 4, 1 + 14 = 25) are Squareful.
Sample input 2
4
1 1 1 1
Sample output 2:-
0
Full screen
Console