N 요소의 배열이 제공됩니다. 목표는 i!=j와 같은 완전제곱합 합계를 갖는 모든 쌍(Arr[i],Arr[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
설명 − 모든 쌍의 합계는 6이며 완전제곱식이 아닙니다.
아래 프로그램에서 사용된 접근 방식은 다음과 같습니다.
-
임의의 숫자로 초기화된 정수 배열 Arr[]을 사용합니다.
-
Arr[]의 길이를 저장하는 변수 n을 사용합니다.
-
countPairs(int arr[], int n) 함수는 배열의 길이를 입력으로 받아 완전제곱수 합계를 갖는 쌍을 반환합니다.
-
쌍의 각 요소에 대해 두 개의 for 루프를 사용하여 배열을 탐색합니다.
-
0<=i
-
arr[i]의 합을 계산하고, arr[j]는 양수입니다.
-
합계의 제곱근을 sqrt(sum)로 계산합니다.
-
이제 sqr-floor(sqr)==0인지 확인하십시오. 즉, 합은 완전제곱수입니다. true인 경우 카운트를 증가시킵니다.
-
모든 루프가 끝나면 합계가 완전제곱수인 총 쌍의 개수가 표시됩니다.
-
카운트를 결과로 반환합니다.
예시
#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