Loading problem...
An array arrangement is considered square-compatible if every pair of consecutive (adjacent) elements in the arrangement sums to a perfect square. A perfect square is an integer that is the square of some integer (e.g., 0, 1, 4, 9, 16, 25, ...).
Given an integer array nums, determine the total count of distinct permutations of nums that satisfy the square-compatible property.
Two permutations arrangement1 and arrangement2 are considered different if there exists at least one index i where arrangement1[i] ≠ arrangement2[i].
Note: Even if the same values exist at different positions, permutations that result in identical orderings are counted only once.
nums = [1,17,8]2The two valid square-compatible arrangements are [1,8,17] and [17,8,1]. In [1,8,17]: 1+8=9=3² and 8+17=25=5². In [17,8,1]: 17+8=25=5² and 8+1=9=3². All other permutations contain at least one adjacent pair whose sum is not a perfect square.
nums = [2,2,2]1Since all elements are identical, there is only one distinct arrangement [2,2,2]. In this arrangement, 2+2=4=2², which is a perfect square. Thus, there is exactly one valid square-compatible permutation.
nums = [0,0,0]1All elements are zeros, so only one unique arrangement exists: [0,0,0]. Here, 0+0=0=0², which is a perfect square. Hence, exactly one valid permutation exists.
Constraints