Welcome to Subscribe On Youtube
Formatted question description: https://leetcode.ca/all/996.html
996. Number of Squareful Arrays (Hard)
Given an array A of non-negative integers, the array is squareful if for every pair of adjacent elements, their sum is a perfect square.
Return the number of permutations of A that are squareful. Two permutations A1 and A2 differ if and only if there is some index i such that A1[i] != A2[i].
Example 1:
Input: [1,17,8] Output: 2 Explanation: [1,8,17] and [17,8,1] are the valid permutations.
Example 2:
Input: [2,2,2] Output: 1
Note:
1 <= A.length <= 120 <= A[i] <= 1e9
Related Topics:
Math, Backtracking, Graph
Similar Questions:
Solution 1. Backtracking
Brute force: next_permutation + squareful check.
Issue: if the leading x elements are not squareful, no matter how the rest of the elements are permutated, the result can’t be squareful. So we need to make sure the permutation is squareful along the way.
Solution: manually implement next_permutation, check if the currently settled subarray is squareful.
Skip this leading section if it’s already not squareful.
// OJ: https://leetcode.com/problems/number-of-squareful-arrays/
// Time: O(N!)
// Space: O(N^2)
class Solution {
int ans = 0;
inline bool isSquare(int n) {
int r = sqrt(n);
return r * r == n;
}
void dfs(vector<int> &A, int start) {
if (start == A.size()) {
++ans;
return;
}
unordered_set<int> s;
for (int i = start; i < A.size(); ++i) {
if (s.count(A[i]) || (start - 1 >= 0 && !isSquare(A[start - 1] + A[i]))) continue;
s.insert(A[i]);
swap(A[start], A[i]);
dfs(A, start + 1);
swap(A[start], A[i]);
}
}
public:
int numSquarefulPerms(vector<int>& A) {
dfs(A, 0);
return ans;
}
};
-
class Solution { public int numSquarefulPerms(int[] A) { int length = A.length; Map<Integer, List<Integer>> graphMap = new HashMap<Integer, List<Integer>>(); Integer[][] memo = new Integer[length][1 << length]; for (int i = 0; i < length; i++) { for (int j = i + 1; j < length; j++) { int sum = A[i] + A[j]; int sqrt = (int) Math.sqrt(sum); if (sqrt * sqrt == sum) { List<Integer> list1 = graphMap.getOrDefault(i, new ArrayList<Integer>()); List<Integer> list2 = graphMap.getOrDefault(j, new ArrayList<Integer>()); list1.add(j); list2.add(i); graphMap.put(i, list1); graphMap.put(j, list2); } } } int[] factorials = new int[13]; factorials[0] = 1; for (int i = 1; i <= 12; i++) factorials[i] = factorials[i - 1] * i; int permutations = 0; for (int i = 0; i < length; i++) permutations += depthFirstSearch(i, 1 << i, length, graphMap, memo); Map<Integer, Integer> countMap = new HashMap<Integer, Integer>(); for (int num : A) { int count = countMap.getOrDefault(num, 0) + 1; countMap.put(num, count); } List<Integer> valuesList = new ArrayList<Integer>(countMap.values()); for (int value : valuesList) permutations /= factorials[value]; return permutations; } public int depthFirstSearch(int node, int visited, int length, Map<Integer, List<Integer>> graphMap, Integer[][] memo) { if (visited == (1 << length) - 1) return 1; if (memo[node][visited] != null) return memo[node][visited]; int permutations = 0; List<Integer> list = graphMap.getOrDefault(node, new ArrayList<Integer>()); for (int next : list) { if (((visited >> next) & 1) == 0) permutations += depthFirstSearch(next, visited | (1 << next), length, graphMap, memo); } memo[node][visited] = permutations; return permutations; } } ############ class Solution { public int numSquarefulPerms(int[] nums) { int n = nums.length; int[][] f = new int[1 << n][n]; for (int j = 0; j < n; ++j) { f[1 << j][j] = 1; } for (int i = 0; i < 1 << n; ++i) { for (int j = 0; j < n; ++j) { if ((i >> j & 1) == 1) { for (int k = 0; k < n; ++k) { if ((i >> k & 1) == 1 && k != j) { int s = nums[j] + nums[k]; int t = (int) Math.sqrt(s); if (t * t == s) { f[i][j] += f[i ^ (1 << j)][k]; } } } } } } long ans = 0; for (int j = 0; j < n; ++j) { ans += f[(1 << n) - 1][j]; } Map<Integer, Integer> cnt = new HashMap<>(); for (int x : nums) { cnt.merge(x, 1, Integer::sum); } int[] g = new int[13]; g[0] = 1; for (int i = 1; i < 13; ++i) { g[i] = g[i - 1] * i; } for (int v : cnt.values()) { ans /= g[v]; } return (int) ans; } } -
// OJ: https://leetcode.com/problems/number-of-squareful-arrays/ // Time: O(N!) // Space: O(N^2) class Solution { int ans = 0; inline bool isSquare(int n) { int r = sqrt(n); return r * r == n; } void dfs(vector<int> &A, int start) { if (start == A.size()) { ++ans; return; } unordered_set<int> s; for (int i = start; i < A.size(); ++i) { if (s.count(A[i]) || (start - 1 >= 0 && !isSquare(A[start - 1] + A[i]))) continue; s.insert(A[i]); swap(A[start], A[i]); dfs(A, start + 1); swap(A[start], A[i]); } } public: int numSquarefulPerms(vector<int>& A) { dfs(A, 0); return ans; } }; -
# 996. Number of Squareful Arrays # https://leetcode.com/problems/number-of-squareful-arrays/ class Solution: def numSquarefulPerms(self, nums: List[int]) -> int: n = len(nums) nums.sort() res = 0 used = [False] * n @cache def good(m): sq = int(math.sqrt(m)) return sq * sq == m def perm(path): nonlocal res if len(path) == n: res += 1 return for i in range(n): if used[i]: continue if i > 0 and nums[i] == nums[i - 1] and not used[i - 1]: continue if len(path) == 0 or (len(path) > 0 and good(path[-1] + nums[i])): used[i] = True perm(path + [nums[i]]) used[i] = False perm([]) return res -
func numSquarefulPerms(nums []int) (ans int) { n := len(nums) f := make([][]int, 1<<n) for i := range f { f[i] = make([]int, n) } for j := range nums { f[1<<j][j] = 1 } for i := 0; i < 1<<n; i++ { for j := 0; j < n; j++ { if i>>j&1 == 1 { for k := 0; k < n; k++ { if i>>k&1 == 1 && k != j { s := nums[j] + nums[k] t := int(math.Sqrt(float64(s))) if t*t == s { f[i][j] += f[i^(1<<j)][k] } } } } } } for j := 0; j < n; j++ { ans += f[(1<<n)-1][j] } g := [13]int{1} for i := 1; i < 13; i++ { g[i] = g[i-1] * i } cnt := map[int]int{} for _, x := range nums { cnt[x]++ } for _, v := range cnt { ans /= g[v] } return }