Số mảng vuông trong C ++

Giả sử chúng ta có một mảng A gồm các số nguyên dương, chúng ta có thể nói rằng mảng đó là bình phương nếu với mọi cặp phần tử liền kề, tổng của chúng là một bình phương hoàn hảo. Chúng ta phải tìm số hoán vị của A là bình phương. Hai hoán vị A1 và A2 sẽ không giống nhau nếu và chỉ khi có một số chỉ số i sao cho A1 [i] không giống A2 [i].

Vì vậy, nếu đầu vào là [3,30,6], thì đầu ra sẽ là 2, vì chúng ta có hai hoán vị như [3,6,30], [30,6,3].

Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -

• Xác định một hàm isSqr (), điều này sẽ mất n,

  • x:=căn bậc hai của n

  • trả về true khi (x * x) giống với n

• Xác định một hàm giải quyết (), điều này sẽ nhận một mảng a, idx,

  • nếu idx bằng với kích thước của a, thì -

    • (tăng số lượng lên 1)

    • trở lại

  • Xác định một tập hợp đã truy cập

  • để khởi tạo i:=idx, khi tôi

    • nếu (idx giống 0 hoặc isSqr (a [idx - 1] + a [i])) và [i] không được truy cập thì -

      • hoán đổi (a [idx], a [i])

      • giải quyết (a, idx + 1)

      • hoán đổi (a [idx], a [i])

      • chèn [i] vào đã ghé thăm

• Từ phương thức chính, thực hiện như sau -

• đếm:=0

• giải quyết (a, 0)

• số lần trả lại

Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -

Ví dụ

#include <bits/stdc++.h>
using namespace std;
typedef long long int lli;
class Solution {
   public:
   int count;
   bool isSqr(lli n){
      lli x = sqrt(n);
      return x * x == n;
   }
   void solve(vector<int>& a, int idx){
      if (idx == a.size()) {
         count++;
         return;
      }
      set<int> visited;
      for (int i = idx; i < a.size(); i++) {
         if ((idx == 0 || isSqr(a[idx - 1] + a[i])) &&
         !visited.count(a[i])) {
            swap(a[idx], a[i]);
            solve(a, idx + 1);
            swap(a[idx], a[i]);
            visited.insert(a[i]);
         }
      }
   }
   int numSquarefulPerms(vector<int>& a){
      count = 0;
      solve(a, 0);
      return count;
   }
};
main(){
   Solution ob;
   vector<int> v = {3,30,6};
   cout << (ob.numSquarefulPerms(v));
}

Đầu vào

{3,30,6}

Đầu ra

2