New update is available. Click here to update.

Number of squareful arrays

HARD

50 mins

9 upvotes

Bit Manipulation

Dynamic Programming

Graph

Solve problems & track your progress

Checkout your overall progress in every topic here

Become

Sensei

in DSA topics

Open the topic and solve more problems associated with it to improve your skills

Check out the skill meter for every topic

See how many problems you are left with to solve for cracking any stage. Score more than zero to get your progress counted.

Problem

Submissions

Number of squareful arrays

Contributed by

Ambuj verma

Hard

0/120

Avg time to solve 50 mins

Success Rate 50 %

9 upvotes

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, Constraints, Images )

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

Sample input 1

3
1 24 3

Sample output 1

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:-

Auto

Console