We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Number of Squareful Arrays

Difficulty: Hard

Problem Description

An array is squareful if the sum of every pair of adjacent elements is a perfect square. Given an integer array nums, return the number of permutations of nums that are squareful. Two permutations perm1 and perm2 are different if there is some index i such that perm1[i] != perm2[i].

Key Insights

  • A perfect square can be determined by checking if the square root of a number is an integer.
  • To efficiently find valid permutations, we can use backtracking combined with a set to track used elements.
  • Duplicates in the input array can lead to duplicate permutations; hence, careful handling of duplicates is necessary.
  • The maximum length of the input array is small (up to 12), which allows for a combinatorial approach to be feasible.

Space and Time Complexity

Time Complexity: O(n! * n) where n is the number of elements in the input array due to generating permutations and checking adjacent sums. Space Complexity: O(n) for the recursion stack and O(n) for storing the permutations.

Solution

To solve the problem, we can use a backtracking approach:

  1. First, generate all unique permutations of the input array using a sorted version of the array to facilitate duplicate handling.
  2. For each permutation, check if it is squareful by ensuring that the sum of each adjacent pair is a perfect square.
  3. Count and return the number of valid squareful permutations.

The main data structure used is a list to hold the current permutation, and we will use a set to track used numbers for efficient lookups.

Code Solutions

import math
from itertools import permutations

def is_perfect_square(x):
    s = int(math.sqrt(x))
    return s * s == x

def is_squareful_array(arr):
    for i in range(len(arr) - 1):
        if not is_perfect_square(arr[i] + arr[i + 1]):
            return False
    return True

def num_squareful_perms(nums):
    count = 0
    unique_perms = set(permutations(sorted(nums)))  # Get unique permutations

    for perm in unique_perms:
        if is_squareful_array(perm):
            count += 1
            
    return count
← Back to All Questions