Welcome to Subscribe On Youtube

996. Number of Squareful Arrays

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].

 

Example 1:

Input: nums = [1,17,8]
Output: 2
Explanation: [1,8,17] and [17,8,1] are the valid permutations.

Example 2:

Input: nums = [2,2,2]
Output: 1

 

Constraints:

• 1 <= nums.length <= 12
• 0 <= nums[i] <= 109

Solutions

• Java
• C++
• Python
• Go

• class Solution {
      public int numSquarefulPerms(int[] nums) {
          int n = nums.length;
          int[][] f = new int[1 << n][n];
          for (int j = 0; j < n; ++j) {
              f[1 << j][j] = 1;
          }
          for (int i = 0; i < 1 << n; ++i) {
              for (int j = 0; j < n; ++j) {
                  if ((i >> j & 1) == 1) {
                      for (int k = 0; k < n; ++k) {
                          if ((i >> k & 1) == 1 && k != j) {
                              int s = nums[j] + nums[k];
                              int t = (int) Math.sqrt(s);
                              if (t * t == s) {
                                  f[i][j] += f[i ^ (1 << j)][k];
                              }
                          }
                      }
                  }
              }
          }
          long ans = 0;
          for (int j = 0; j < n; ++j) {
              ans += f[(1 << n) - 1][j];
          }
          Map<Integer, Integer> cnt = new HashMap<>();
          for (int x : nums) {
              cnt.merge(x, 1, Integer::sum);
          }
          int[] g = new int[13];
          g[0] = 1;
          for (int i = 1; i < 13; ++i) {
              g[i] = g[i - 1] * i;
          }
          for (int v : cnt.values()) {
              ans /= g[v];
          }
          return (int) ans;
      }
  }
  

• class Solution {
  public:
      int numSquarefulPerms(vector<int>& nums) {
          int n = nums.size();
          int f[1 << n][n];
          memset(f, 0, sizeof(f));
          for (int j = 0; j < n; ++j) {
              f[1 << j][j] = 1;
          }
          for (int i = 0; i < 1 << n; ++i) {
              for (int j = 0; j < n; ++j) {
                  if ((i >> j & 1) == 1) {
                      for (int k = 0; k < n; ++k) {
                          if ((i >> k & 1) == 1 && k != j) {
                              int s = nums[j] + nums[k];
                              int t = sqrt(s);
                              if (t * t == s) {
                                  f[i][j] += f[i ^ (1 << j)][k];
                              }
                          }
                      }
                  }
              }
          }
          long long ans = 0;
          for (int j = 0; j < n; ++j) {
              ans += f[(1 << n) - 1][j];
          }
          unordered_map<int, int> cnt;
          for (int x : nums) {
              ++cnt[x];
          }
          int g[13] = {1};
          for (int i = 1; i < 13; ++i) {
              g[i] = g[i - 1] * i;
          }
          for (auto& [_, v] : cnt) {
              ans /= g[v];
          }
          return ans;
      }
  };
  

• class Solution:
      def numSquarefulPerms(self, nums: List[int]) -> int:
          n = len(nums)
          f = [[0] * n for _ in range(1 << n)]
          for j in range(n):
              f[1 << j][j] = 1
          for i in range(1 << n):
              for j in range(n):
                  if i >> j & 1:
                      for k in range(n):
                          if (i >> k & 1) and k != j:
                              s = nums[j] + nums[k]
                              t = int(sqrt(s))
                              if t * t == s:
                                  f[i][j] += f[i ^ (1 << j)][k]
  
          ans = sum(f[(1 << n) - 1][j] for j in range(n))
          for v in Counter(nums).values():
              ans //= factorial(v)
          return ans
  
  

• func numSquarefulPerms(nums []int) (ans int) {
  	n := len(nums)
  	f := make([][]int, 1<<n)
  	for i := range f {
  		f[i] = make([]int, n)
  	}
  	for j := range nums {
  		f[1<<j][j] = 1
  	}
  	for i := 0; i < 1<<n; i++ {
  		for j := 0; j < n; j++ {
  			if i>>j&1 == 1 {
  				for k := 0; k < n; k++ {
  					if i>>k&1 == 1 && k != j {
  						s := nums[j] + nums[k]
  						t := int(math.Sqrt(float64(s)))
  						if t*t == s {
  							f[i][j] += f[i^(1<<j)][k]
  						}
  					}
  				}
  			}
  		}
  	}
  	for j := 0; j < n; j++ {
  		ans += f[(1<<n)-1][j]
  	}
  	g := [13]int{1}
  	for i := 1; i < 13; i++ {
  		g[i] = g[i-1] * i
  	}
  	cnt := map[int]int{}
  	for _, x := range nums {
  		cnt[x]++
  	}
  	for _, v := range cnt {
  		ans /= g[v]
  	}
  	return
  }
  

All Problems

All Solutions