Number of Squareful Arrays — LeetCode 996 Python Solution
HardBit ManipulationArrayHash TableMathDynamic ProgrammingBacktrackingBitmask
- Problem
- #996
- Pattern
- Backtracking
- Reading time
- 4 min
- Source
- leetcode.com
The problem
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.
Example
- Input
- nums = [1,17,8]
- Output
- 2
- Explanation
- [1,8,17] and [17,8,1] are the valid permutations.
Python solution
Python
class Solution:
def numSquarefulPerms(self, nums: List[int]) -> int:
n = len(nums)
f = [[0] * n for _ in range(1 << n)]
for j in range(n):
f[1 << j][j] = 1
for i in range(1 << n):
for j in range(n):
if i >> j & 1:
for k in range(n):
if (i >> k & 1) and k != j:
s = nums[j] + nums[k]
t = int(sqrt(s))
if t * t == s:
f[i][j] += f[i ^ (1 << j)][k]
ans = sum(f[(1 << n) - 1][j] for j in range(n))
for v in Counter(nums).values():
ans //= factorial(v)
return ansComplexity
| Measure | Complexity |
|---|---|
| Time | O(n) |
| Space | O(n) auxiliary |
Pattern: Backtracking
Build candidates one choice at a time and abandon a branch the moment it cannot work. LeetCode 996. Number of Squareful Arrays is filed here because LeetCode tags it Backtracking, which is the vocabulary this hub collects.
The backtracking guide has the Python template for the pattern and the 105 LeetCode problems that use it.
Related problems
Frequently asked questions
- How hard is LeetCode 996. Number of Squareful Arrays?
- LeetCode 996. Number of Squareful Arrays is rated Hard on LeetCode.
- What is the time complexity of LeetCode 996. Number of Squareful Arrays?
- The Python solution on this page runs in O(n).
- What is the space complexity of LeetCode 996. Number of Squareful Arrays?
- The Python solution on this page uses O(n) auxiliary space.
- What topics does LeetCode 996. Number of Squareful Arrays cover?
- LeetCode 996. Number of Squareful Arrays is tagged Bit Manipulation, Array, Hash Table, Math, Dynamic Programming, Backtracking and Bitmask on LeetCode.