Number of Squareful Arrays

Number of Squareful Arrays

What is this problem about?

The Number of Squareful Arrays problem asks you to count permutations of an array where every pair of adjacent elements sums to a perfect square. This hard coding problem uses bitmask DP (or backtracking) similar to the Hamiltonian path count, where nodes are array elements and edges exist between pairs summing to a perfect square.

Why is this asked in interviews?

Apple and Google ask this because it combines graph modeling (elements as nodes, squareful pairs as edges) with bitmask DP for Hamiltonian path counting — or pruned backtracking with duplicate handling. The array, math, bitmask, hash table, backtracking, bit manipulation, and dynamic programming interview pattern is fully exercised.

Algorithmic pattern used

Bitmask DP (Hamiltonian path). Model elements as graph nodes with edges between elements that sum to a perfect square. dp[mask][last] = number of paths visiting exactly the elements in mask, ending at element last. Transition: for each unvisited neighbor of last that sums to a perfect square, update the next state. Handle duplicate elements carefully using a frequency map approach.

Example explanation

Array: [1, 8, 17, 1]. Squareful pairs: (1,8)→9=3², (8,17)→25=5², (17,8)→25=5², (8,1)→9=3². Valid permutations:

• [1,8,17,1]: 1+8=9✓, 8+17=25✓, 17+1=18✗. Invalid.
• [1,8,1,16]? Can't, 16 not in array. Try all 12 orderings of [1,1,8,17]: Valid paths: only [1,8,1,...] → but 1+8=9✓, 8+1=9✓, 1+?... need 17: 1+17=18✗. Actually: 17+8=25✓, 8+1=9✓. [17,8,1,?]→next 1: 1+1=2✗. Hmm. Answer for [1,17,8] (without second 1): 1+17=18✗, 17+8=25✓, 8+1=9✓. Try [1,8,17]? 1+8=9✓,8+17=25✓. Valid! With duplicates [1,1,8,17]: answer = 2.

Common mistakes candidates make

• Not handling duplicate elements (permutations of duplicates should not be double-counted).
• Checking sqrt with floating point (use int(sqrt(x))²==x for precision).
• Using O(n!) backtracking without bitmask DP for larger n.
• Building the graph adjacency incorrectly (edge between indices, not values, for duplicates).

Interview preparation tip

Squareful array is a Hamiltonian path counting problem on a small graph. The bitmask DP template: dp[mask][last] = count of paths visiting the subset in mask and ending at last. Transition: add any unvisited neighbor. For duplicate handling, process elements by frequency groups. Practice the Hamiltonian path bitmask DP on TSP and similar problems — this is the standard approach for n ≤ 20.