Neighbors That Sum to a Square
Put all the numbers of nums in a row so that every two neighbors add up to a perfect square (0, 1, 4, 9, 16 and so on).
Return how many different rows there are. Two rows are different when some position holds a different value, so swapping two equal numbers does not make a new row. A row of one number always counts.
Example 1
nums [2,7,9]
returns 2
2 + 7 = 9 and 7 + 9 = 16, so [2, 7, 9] and [9, 7, 2] work. 2 and 9 cannot be neighbors.
Example 2
nums [8,8,8]
returns 1
8 + 8 = 16, and every order of three equal numbers is the same row.
Example 3
nums [5,4,11,20]
returns 0
Only 5 pairs up with the others, and it cannot stand next to all three of them.
Constraints
1 <= len(nums) <= 120 <= nums[i] <= 10**6
Write it in your browser, against the clock. The model solution, stepped through line by line, comes after.
More Recursion problems
- Queens Around ObstaclesHard
- Signs Between the DigitsHard
- Spell It With TilesHard
- Swap the Balanced PiecesHard
- Times Before PlusHard
- Valleys in the Folded StripHard
- Count the BoxesBeginner
- Digit TallyBeginner