Skip to content

996. Number of Squareful Arrays

Description

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 <= 12
  • 0 <= nums[i] <= 109

 

Solutions

Solution: Backtracking + Bitmask

  • Time complexity: O(n!)
  • Space complexity: O(n)

 

JavaScript

js
/**
 * @param {number[]} nums
 * @return {number}
 */
const numSquarefulPerms = function (nums) {
  const n = nums.length;
  let result = 0;

  const findSquarefulPrem = (last, used, length) => {
    if (length === n) {
      result += 1;
      return;
    }

    for (let index = 0; index < n; index++) {
      if ((1 << index) & used) continue;
      const num = nums[index];
      const isPreviousUsed = (1 << (index - 1)) & used;

      if (num === nums[index - 1] && !isPreviousUsed) continue;
      const sum = last + num;

      if (!Number.isInteger(Math.sqrt(sum))) continue;
      findSquarefulPrem(num, (1 << index) | used, length + 1);
    }
  };

  nums.sort((a, b) => a - b);

  for (let index = 0; index < n; index++) {
    const num = nums[index];

    if (num === nums[index - 1]) continue;
    findSquarefulPrem(num, 1 << index, 1);
  }
  return result;
};

Released under the MIT license