정수형 요소의 정렬된 배열과 정수 변수 x가 주어지고 주어진 배열에서 쌍을 형성하고 쌍에 있는 요소의 곱을 계산하고 계산된 곱이 k보다 작은지 여부를 확인하는 것이 작업입니다.
입력
int arr[] = {2, 7, 1, 0, 8}, int k = 10 출력
Count of pairs in a sorted array whose product is less than k are: 7
설명
The pairs that can be formed from the given array are: (2, 7) = 14(greater than k), (2, 1) = 2(less than k), (2, 0) = 0(less than k), (2, 8) = 16(greater than k), (7, 1) = 7(less than k), (7, 0) = 0(less than k), (7, 8) = 56(greater than k), (1, 0) = 0(less than k), (1, 8) = 8(less than k), (0, 8) = 0(less than k). So, the count of pairs with sum less than k are 7.
입력
int arr[] = {2, 4, 6, 8}, int k = 10 출력
Count of pairs in a sorted array whose product is less than k are: 1
설명
The pairs that can be formed from the given array are: (2, 4) = 8(less than k), (2, 6) = 12(greater than k), (2, 8) = 16(greater than k), (4, 6) = 24(greater than x), (4, 8) = 32(greater than k), (6, 8) = 48(greater than k). So, the count of pairs with products less than k is 1.
아래 프로그램에서 사용된 접근 방식은 다음과 같습니다.
주어진 문제를 해결하기 위한 여러 가지 접근 방식, 즉 순진한 접근 방식과 효율적인 접근 방식이 있을 수 있습니다. 먼저 순진한 접근 방식을 살펴보겠습니다. .
-
정수 요소의 배열을 입력하고 배열의 크기를 계산하고 데이터를 함수에 전달
-
k보다 작은 제품과의 쌍의 개수를 저장하기 위해 임시 변수 개수를 선언합니다.
-
배열의 크기까지 i에서 0까지 FOR 루프 시작
-
루프 내에서 배열의 크기까지 j에서 i + 1까지 FOR 또 다른 루프를 시작합니다.
-
루프 내에서 곱을 arr[i] * arr[j]로 계산하고 IF product
-
개수 반환
-
결과를 인쇄합니다.
효율적인 접근
-
정수 요소의 배열을 입력하고 배열의 크기를 계산하고 데이터를 함수에 전달
-
합이 x보다 작은 쌍의 개수를 저장하기 위해 임시 변수 개수를 선언합니다.
-
arr_0을 0으로 설정하고 arr_1을 size-1로 설정
-
arr_0에서 arr_1까지 FOR 루프 시작
-
루프 내에서 IF arr[arr_0] * arr[arr_1]
-
개수 반환
-
결과를 인쇄하십시오.
예(순진한 접근 방식)
#include <iostream>
using namespace std;
int pair_product(int arr[], int size, int k){
int count = 0;
int product = 1;
for(int i = 0 ; i<size ; i++){
for(int j = i+1; j<size; j++){
product = arr[i] * arr[j];
if(product < k){
count++;
}
}
}
return count;
}
int main(){
int arr[] = {5, 8, 2, 1, 3};
int size = sizeof(arr) / sizeof(arr[0]);
int k = 10;
cout<<"Count of pairs in a sorted array whose product is less than k are: "<<pair_product(arr, size, k);
return 0;
} 출력
위의 코드를 실행하면 다음 출력이 생성됩니다 -
Count of pairs in a sorted array whose product is less than k are: 5
예(효율적인 접근)
#include <iostream>
using namespace std;
int pair_product(int arr[], int size, int k){
int arr_0 = 0;
int arr_1 = size-1;
int count = 0;
int product = 1;
while(arr_0 < arr_1){
product = arr[arr_0] * arr[arr_1];
if (product < k){
count = count + (arr_1 - arr_0);
arr_0++;
}
else{
arr_1--;
}
}
return count;
}
int main(){
int arr[] = {1, 3, 4, 2, 1};
int size = sizeof(arr) / sizeof(arr[0]);
int k = 5;
cout<<"Count of pairs in a sorted array whose product is less than k are: "<<pair_product(arr, size, k);
return 0;
} 출력
위의 코드를 실행하면 다음 출력이 생성됩니다 -
Count of pairs in a sorted array whose product is less than k are: 10