Algorithm
Problem Name: 996. Number of Squareful Arrays
An array is squareful if the sum of every pair of adjacent elements is a perfect square.
Given an integer array nums, return the number of permutations of nums that are squareful.
Two permutations perm1 and perm2 are different if there is some index i such that perm1[i] != perm2[i].
Example 1:
Input: nums = [1,17,8] Output: 2 Explanation: [1,8,17] and [17,8,1] are the valid permutations.
Example 2:
Input: nums = [2,2,2] Output: 1
Constraints:
1 <= nums.length <= 120 <= nums[i] <= 109
Code Examples
#1 Code Example with Java Programming
Code -
Java Programming
class Solution {
public int numSquarefulPerms(int[] nums) {
Arrays.sort(nums);
int[] count = {0};
backtrack(new ArrayList < >(), nums, new boolean[nums.length], -1, count);
return count[0];
}
private void backtrack(List < Integer> temp, int[] nums, boolean[] used, int lastNumber, int[] count) {
if (temp.size() == nums.length){
count[0]++;
return;
}
for (int i = 0; i < nums.length; i++){
if (used[i] || (i > 0 && nums[i] == nums[i - 1] && !used[i - 1])){
continue;
}
if (lastNumber != -1) {
if (!isSquare(nums[i] + lastNumber)) {
continue;
}
}
used[i] = true;
temp.add(nums[i]);
backtrack(temp, nums, used, nums[i], count);
temp.remove(temp.size() - 1);
used[i] = false;
}
}
private boolean isSquare(int num) {
int squareRoot = (int) Math.sqrt(num);
return squareRoot * squareRoot == num;
}
}
Input
nums = [1,17,8]
Output
2
#2 Code Example with Javascript Programming
Code -
Javascript Programming
const numSquarefulPerms = function (A) {
const cntMap = {}
const squareMap = {}
let cnt = 0
for (let num of A) {
if (!cntMap.hasOwnProperty(num)) {
cntMap[num] = 1
squareMap[num] = new Set()
} else {
cntMap[num] = cntMap[num] + 1
}
}
for (let num1 of Object.keys(cntMap)) {
for (let num2 of Object.keys(cntMap)) {
let c = Math.sqrt(+num1 + +num2)
if (c === Math.floor(c)) {
squareMap[num1].add(+num2)
squareMap[num2].add(+num1)
}
}
}
for (let num of Object.keys(cntMap)) {
countPerm(num, A.length - 1)
}
return cnt
function countPerm(num, left) {
cntMap[num] = cntMap[num] - 1
if (left === 0) {
cnt++
} else {
for (let next of squareMap[num]) {
if (cntMap[next] !== 0) {
countPerm(next, left - 1)
}
}
}
cntMap[num] = cntMap[num] + 1
}
}
Input
nums = [1,17,8]
Output
2
#3 Code Example with Python Programming
Code -
Python Programming
class Solution:
def numSquarefulPerms(self, A: List[int]) -> int:
self.res = 0
def dfs(cnt, num):
if not cnt:
self.res += 1
for new in nex[num]:
if cnt[new]:
cnt[new] -= 1
if not cnt[new]:
cnt.pop(new)
dfs(cnt, new)
cnt[new] += 1
nex = collections.defaultdict(set)
cnt = collections.Counter(A)
for a, b in itertools.permutations(A, 2):
if not (a + b) ** 0.5 % 1:
nex[a].add(b)
nex[b].add(a)
for a in set(A):
cnt[a] -= 1
if not cnt[a]:
cnt.pop(a)
dfs(cnt, a)
cnt[a] += 1
return self.res
Input
nums = [2,2,2]
Output
1