Chúng ta được cung cấp với một mảng N phần tử. Mục đích là tìm số lượng tất cả các cặp (Arr [i], Arr [j]) có tổng là một hình vuông hoàn hảo sao cho i! =J. Đó là Arr [i] + Arr [j] là một hình vuông hoàn hảo.
Chúng ta sẽ làm điều này bằng cách tính tổng của các cặp và kiểm tra xem căn bậc hai của tổng đó có bằng giá trị sàn của căn bậc hai hay không. sqrt (Arr [i] + Arr [j]) - tầng (sqrt (Arr [i] + Arr [j]) ==0.
Hãy cùng hiểu với các ví dụ.
Đầu vào - Arr [] ={4,3,2,1,2,4} N =6
Đầu ra - Đếm các cặp có tổng là bình phương hoàn hảo - 2
Giải thích -
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.
Đầu vào - Arr [] ={3,3,3,3,3} N =5
Đầu ra - Đếm các cặp có tổng là bình phương hoàn hảo - 0
Giải thích - Tất cả các cặp đều có tổng =6, đây không phải là một bình phương hoàn hảo.
Phương pháp tiếp cận được sử dụng trong chương trình dưới đây như sau
-
Chúng tôi lấy một mảng số nguyên Arr [] được khởi tạo với các số ngẫu nhiên.
-
Lấy một biến n lưu trữ độ dài của Arr [].
-
Hàm countPairs (int arr [], int n) nhận một mảng, độ dài của nó làm đầu vào và trả về các cặp có tổng là một hình vuông hoàn hảo.
-
Traverse mảng sử dụng hai vòng lặp for cho mỗi phần tử của cặp.
-
Vòng ngoài từ 0 <=i
-
Tính tổng arr [i], arr [j] là số dương.
-
Tính căn bậc hai của tổng dưới dạng sqrt (sum).
-
Bây giờ hãy kiểm tra xem sqr-floor (sqr) ==0. Có nghĩa là tổng là một hình vuông hoàn hảo. Nếu số gia tăng đúng.
-
Ở cuối tất cả các vòng đếm sẽ có tổng số các cặp có tổng là bình phương hoàn hảo.
-
Trả về kết quả là số lượng.
Ví dụ
#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;
} Đầu ra
Nếu chúng ta chạy đoạn mã trên, nó sẽ tạo ra kết quả sau -
Pairs whose product is power of 2:6