Number of Squareful Arrays

HardBacktrackingbacktracking

Solve this the way you would in the interview: out loud, on a timer, with an AI interviewer asking follow-ups while you code. You get a scored report at the end.

Practice this as a mock interviewFree to start, no account needed

Problem

An array is **squareful** if the sum of every pair of adjacent elements is a perfect square. An array with a single element is squareful. Given an integer array nums, return the number of **distinct** permutations of nums that are squareful. Two permutations are distinct if they differ at some index as value sequences, so swapping two equal values does not create a new permutation.

Examples

Input: nums = [1,17,8]
Output: 2
[1,8,17] (sums 9 and 25) and [17,8,1] (sums 25 and 9).
Input: nums = [2,2,2]
Output: 1
Every adjacent sum is 4 and there is only one distinct arrangement.

Constraints

  • 1 <= nums.length <= 12
  • 0 <= nums[i] <= 10^9

What the interviewer grades

A correct solution is one of five scores. The report also grades problem understanding (did you clarify inputs and edge cases before coding), problem solving, communication while you work, code quality, and testing. See a sample report, or read up on the pattern in the lessons.

More backtracking problems