เราได้รับอาร์เรย์ขององค์ประกอบ 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[] ที่เริ่มต้นด้วยตัวเลขสุ่ม
-
ใช้ตัวแปร 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 prod=0;
for(int i=0;i<n-1;i++){
for(int j=i+1;j<n;j++){
prod=arr[i]*arr[j];
if( ceil(log2(prod))==floor(log2(prod)) ){
count++;
//cout<<endl<<"a :"<<arr[i]<<" b :"<<arr[j]; //to print
}
}
}
return count;
}
int main(){
int arr[] = { 2, 5, 8, 16, 128 };
int n = sizeof(arr) / sizeof(arr[0]);
cout <<endl<<"Pairs whose product is power of 2:"<<countPairs(arr, n);
return 0;
} ผลลัพธ์
หากเราเรียกใช้โค้ดข้างต้น มันจะสร้างผลลัพธ์ต่อไปนี้ -
Pairs whose product is power of 2:6
