Number of squareful arrays

Hard
0/120
Average time to solve is 50m
profile
Contributed by
18 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 )
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
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
Hint

 Check all permutations.

Approaches (2)
Brute force

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’.
Time Complexity

O(N! * N)  where ‘N’ is the size of the array.

 

For the array of size ‘N’, there are N! possible permutations and we are checking all permutations for which we have to iterate through the array of size ‘N’, and for checking square root we use sqrt function. So our time complexity is N! * N = O(N! * N)

Space Complexity

O(1),

 

No extra space is used.

Code Solution
(100% EXP penalty)
Number of squareful arrays
Full screen
Console