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. 1 <= A.length <= 12
2. 0 <= A[i] <= 1e9

## Solution1: DFS

Try all permutations with pruning.

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

## Solution 2: DP Hamiltonian Path

dp[s][i] := # of ways to reach state s (binary mask of nodes visited) that ends with node i

dp[s | (1 << j)][j] += dp[s][i] if g[i][j]

Time complexity: O(n^2*2^n)
Space complexity: O(2^n)

## Related Problems

In an array A containing only 0s and 1s, a K-bit flip consists of choosing a (contiguous) subarray of length K and simultaneously changing every 0 in the subarray to 1, and every 1 in the subarray to 0.

Return the minimum number of K-bit flips required so that there is no 0 in the array.  If it is not possible, return -1.

Example 1:

Input: A = [0,1,0], K = 1
Output: 2
Explanation: Flip A[0], then flip A[2].


Example 2:

Input: A = [1,1,0], K = 2
Output: -1
Explanation: No matter how we flip subarrays of size 2, we can't make the array become [1,1,1].


Example 3:

Input: A = [0,0,0,1,0,1,1,0], K = 3
Output: 3
Explanation:
Flip A[0],A[1],A[2]: A becomes [1,1,1,1,0,1,1,0]
Flip A[4],A[5],A[6]: A becomes [1,1,1,1,1,0,0,0]
Flip A[5],A[6],A[7]: A becomes [1,1,1,1,1,1,1,1]


Note:

1. 1 <= A.length <= 30000
2. 1 <= K <= A.length

## Solution: Greedy

From left most, if there is a 0, that bit must be flipped since the right ones won’t affect left ones.

Time complexity: O(nk) -> O(k)
Space complexity: O(1)

## C++ / O(n)

In a given grid, each cell can have one of three values:

• the value 0 representing an empty cell;
• the value 1 representing a fresh orange;
• the value 2 representing a rotten orange.

Every minute, any fresh orange that is adjacent (4-directionally) to a rotten orange becomes rotten.

Return the minimum number of minutes that must elapse until no cell has a fresh orange.  If this is impossible, return -1instead.

Example 1:

Input: [[2,1,1],[1,1,0],[0,1,1]]
Output: 4


Example 2:

Input: [[2,1,1],[0,1,1],[1,0,1]]
Output: -1
Explanation:  The orange in the bottom left corner (row 2, column 0) is never rotten, because rotting only happens 4-directionally.


Example 3:

Input: [[0,2]]
Output: 0
Explanation:  Since there are already no fresh oranges at minute 0, the answer is just 0.


Note:

1. 1 <= grid.length <= 10
2. 1 <= grid[0].length <= 10
3. grid[i][j] is only 01, or 2.

## Solution: BFS

Time complexity: O(mn)
Space complexity: O(mn)

## C++

In a binary tree, the root node is at depth 0, and children of each depth k node are at depth k+1.

Two nodes of a binary tree are cousins if they have the same depth, but have different parents.

We are given the root of a binary tree with unique values, and the values x and y of two different nodes in the tree.

Return true if and only if the nodes corresponding to the values x and y are cousins.

Example 1:

Input: root = [1,2,3,4], x = 4, y = 3
Output: false


Example 2:

Input: root = [1,2,3,null,4,null,5], x = 5, y = 4
Output: true


Example 3:

Input: root = [1,2,3,null,4], x = 2, y = 3
Output: false

Note:

1. The number of nodes in the tree will be between 2 and 100.
2. Each node has a unique integer value from 1 to 100.

## Solution: Preorder traversal

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

## Python3

Mission News Theme by Compete Themes.