จำนวน Squareful Array ใน C++

สมมติว่าเรามีอาร์เรย์ A ของจำนวนเต็มบวก เราสามารถพูดได้ว่าอาร์เรย์เป็นกำลังสอง ถ้าสำหรับทุกคู่ขององค์ประกอบที่อยู่ติดกัน ผลรวมของมันเป็นกำลังสองสมบูรณ์ เราต้องหาจำนวนการเรียงสับเปลี่ยนของ A ที่เป็นกำลังสอง การเรียงสับเปลี่ยนสองแบบ A1 และ A2 จะไม่เหมือนกันก็ต่อเมื่อมีดัชนี i บางอย่างที่ทำให้ A1[i] ไม่เหมือนกับ A2[i]

ดังนั้น หากอินพุตเป็น [3,30,6] เอาต์พุตจะเป็น 2 เนื่องจากเรามีการเรียงสับเปลี่ยนสองแบบ เช่น [3,6,30], [30,6,3]

เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -

• กำหนดฟังก์ชัน isSqr() ซึ่งจะใช้เวลา n

  • x :=รากที่สองของ n

  • คืนค่า จริง เมื่อ (x * x) เหมือนกับ n

• กำหนดฟังก์ชัน Solve() ซึ่งจะใช้อาร์เรย์ a, idx,

  • ถ้า idx เท่ากับขนาด a แล้ว −

    • (เพิ่มจำนวนขึ้น 1)

    • กลับ

  • กำหนดการเยี่ยมชมหนึ่งชุด

  • สำหรับการเริ่มต้น i :=idx เมื่อฉัน <ขนาดของ a อัปเดต (เพิ่ม i ขึ้น 1) ทำ -

    • ถ้า (idx เหมือนกับ 0 หรือ isSqr(a[idx - 1] + a[i])) และ a[i] ไม่ได้ถูกเข้าชม −

      • สลับ (a[idx], a[i])

      • แก้(a, idx + 1)

      • สลับ (a[idx], a[i])

      • ใส่ a[i] เข้าไป

• จากวิธีหลัก ให้ทำดังนี้ −

• นับ :=0

• แก้(a, 0)

• จำนวนคืน

ให้เราดูการใช้งานต่อไปนี้เพื่อความเข้าใจที่ดีขึ้น -

ตัวอย่าง

#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));
}

อินพุต

{3,30,6}

ผลลัพธ์

2