การนับคู่ในอาร์เรย์ที่ผลรวมเป็นกำลังสองสมบูรณ์ใน C++

เราได้รับอาร์เรย์ขององค์ประกอบ N เป้าหมายคือการหาจำนวนคู่ทั้งหมด (Arr[i],Arr[j]) ซึ่งมีผลรวมที่เป็นกำลังสองสมบูรณ์เช่น i!=j นั่นคือ Arr[i]+Arr[j] เป็นสี่เหลี่ยมจัตุรัสที่สมบูรณ์แบบ

เราจะทำสิ่งนี้โดยการคำนวณผลรวมของคู่และตรวจสอบว่ารากที่สองของผลรวมนั้นเท่ากับมูลค่าพื้นของรากที่สองหรือไม่ sqrt(Arr[i]+Arr[j])-floor( sqrt(Arr[i]+Arr[j] )==0.

มาทำความเข้าใจกับตัวอย่างกัน

ป้อนข้อมูล − Arr[]={ 4,3,2,1,2,4 } N=6

ผลผลิต − นับคู่ที่มีผลรวมเป็นกำลังสองสมบูรณ์ − 2

คำอธิบาย −

Arr[1]+Arr[3]=4, sqrt(4)-floor(4)=0 4 is a perfect square.
Arr[2]+Arr[4]=4, sqrt(4)-floor(4)=0 4 is a perfect square.
Rest all pairs have sum 7,6,5,8 which are not perfect squares.

ป้อนข้อมูล − Arr[]={ 3,3,3,3,3} N=5

ผลผลิต − นับคู่ที่มีผลรวมเป็นกำลังสองสมบูรณ์ − 0

คำอธิบาย − ทุกคู่มีค่า sum=6 ซึ่งไม่ใช่กำลังสองสมบูรณ์

แนวทางที่ใช้ในโปรแกรมด้านล่างมีดังนี้

• เราใช้อาร์เรย์จำนวนเต็ม Arr[] ที่เริ่มต้นด้วยตัวเลขสุ่มสำหรับขนาดของถุงมือ> 0

• ใช้ตัวแปร n ซึ่งเก็บความยาวของ Arr[].

• ฟังก์ชัน countPairs(int arr[], int n) รับอาร์เรย์ความยาวเป็นอินพุตและส่งกลับคู่ที่มีผลรวมซึ่งเป็นกำลังสองสมบูรณ์

• Traverse array ใช้ two for loops สำหรับแต่ละองค์ประกอบของคู่

• วงนอกจาก 0<=i

• คำนวณผลรวมของ arr[i], arr[j] เป็นค่าบวก

• คำนวณรากที่สองของผลรวมเป็น sqrt(ผลรวม)

• ตอนนี้ตรวจสอบว่า sqr-floor(sqr)==0 หรือไม่ ซึ่งหมายความว่าผลรวมเป็นกำลังสองสมบูรณ์ ถ้านับเพิ่มจริง

• เมื่อสิ้นสุดการวนซ้ำทั้งหมดจะนับจำนวนคู่ทั้งหมดที่มีผลรวมซึ่งเป็นกำลังสองสมบูรณ์

• คืนค่าการนับเป็นผลลัพธ์

ตัวอย่าง

#include <bits/stdc++.h>
#include <math.h>
using namespace std;
int countPairs(int arr[], int n){
   int count=0;
   int sum=0;
   double sqr=0;
   for(int i=0;i<n-1;i++){
      for(int j=i+1;j<n;j++){
         sum=arr[i]+arr[j];
         sqr=sqrt(sum);
         if( sqr-floor(sqr)==0 ){
            count++;
            //cout<<endl<<"a :"<<arr[i]<<" b :"<<arr[j]; //to print
         }
      }
   }
   return count;
}
int main(){
   int arr[] = { 1, 2, 4, 8, 5, 6 };
   // Size of arr[]
   int n = sizeof(arr) / sizeof(int);
   cout <<endl<<"Pairs whose sum is perfect square :"<<countPairs(arr, n);
   return 0;
}

ผลลัพธ์

หากเราเรียกใช้โค้ดข้างต้น มันจะสร้างผลลัพธ์ต่อไปนี้ -

Pairs whose sum is perfect square :2